gram_schmidt.cpp File Reference

Gram Schmidt Orthogonalisation Process More...

#include <array>
#include <cassert>
#include <cmath>
#include <iostream>
#include "math.h"

Include dependency graph for gram_schmidt.cpp:

Go to the source code of this file.

Namespaces
namespace	numerical_methods
	for assert
namespace	gram_schmidt
	Functions for Gram Schmidt Orthogonalisation Process

Functions
double	numerical_methods::gram_schmidt::dot_product (const std::array< double, 10 > &x, const std::array< double, 10 > &y, const int &c)
double	numerical_methods::gram_schmidt::projection (const std::array< double, 10 > &x, const std::array< double, 10 > &y, const int &c)
void	numerical_methods::gram_schmidt::display (const int &r, const int &c, const std::array< std::array< double, 10 >, 20 > &B)
void	numerical_methods::gram_schmidt::gram_schmidt (int r, const int &c, const std::array< std::array< double, 10 >, 20 > &A, std::array< std::array< double, 10 >, 20 > B)
static void	test ()
int	main ()
	Main Function.

Detailed Description

Gram Schmidt Orthogonalisation Process

Takes the input of Linearly Independent Vectors, returns vectors orthogonal to each other.

Algorithm

Take the first vector of given LI vectors as first vector of Orthogonal vectors. Take projection of second input vector on the first vector of Orthogonal vector and subtract it from the 2nd LI vector. Take projection of third vector on the second vector of Othogonal vectors and subtract it from the 3rd LI vector. Keep repeating the above process until all the vectors in the given input array are exhausted.

For Example: In R2, Input LI Vectors={(3,1),(2,2)} then Orthogonal Vectors= {(3, 1),(-0.4, 1.2)}

Have defined maximum dimension of vectors to be 10 and number of vectors taken is 20. Please do not give linearly dependent vectors

Author

Akanksha Gupta

Definition in file gram_schmidt.cpp.

Function Documentation

display()

void numerical_methods::gram_schmidt::display	(	const int &	r,
		const int &	c,
		const std::array< std::array< double, 10 >, 20 > &	B )

Function to print the orthogonalised vector

Parameters

r	number of vectors
c	dimenaion of vectors
B	stores orthogonalised vectors

Returns

void

Definition at line 101 of file gram_schmidt.cpp.

                                                          {
    for (int i = 0; i < r; ++i) {
        std::cout << "Vector " << i + 1 << ": ";
        for (int j = 0; j < c; ++j) {
            std::cout << B[i][j] << " ";
        }
        std::cout << '\n';
    }
}

dot_product()

double numerical_methods::gram_schmidt::dot_product	(	const std::array< double, 10 > &	x,
		const std::array< double, 10 > &	y,
		const int &	c )

Dot product function. Takes 2 vectors along with their dimension as input and returns the dot product.

Parameters

x	vector 1
y	vector 2
c	dimension of the vectors

Returns

sum

Definition at line 59 of file gram_schmidt.cpp.

                                                                {
    double sum = 0;
    for (int i = 0; i < c; ++i) {
        sum += x[i] * y[i];
    }
    return sum;
}

gram_schmidt()

void numerical_methods::gram_schmidt::gram_schmidt	(	int	r,
		const int &	c,
		const std::array< std::array< double, 10 >, 20 > &	A,
		std::array< std::array< double, 10 >, 20 >	B )

Function for the process of Gram Schimdt Process

Parameters

r	number of vectors
c	dimension of vectors
A	stores input of given LI vectors
B	stores orthogonalised vectors

Returns

void

we check whether appropriate dimensions are given or not.

First vector is copied as it is.

array to store projections

First initialised to zero

to store previous projected array

to store the factor by which the previous array will change

projected array created

we take the projection with all the previous vector and add them.

subtract total projection vector from the input vector

Definition at line 121 of file gram_schmidt.cpp.

                                                        {
    if (c < r) {  
        std::cout << "Dimension of vector is less than number of vector, hence "
                     "\n first "
                  << c << " vectors are orthogonalised\n";
        r = c;
    }
 
    int k = 1;
 
    while (k <= r) {
        if (k == 1) {
            for (int j = 0; j < c; j++)
                B[0][j] = A[0][j];  
        }
 
        else {
            std::array<double, 10>
                all_projection{};  
            for (int i = 0; i < c; ++i) {
                all_projection[i] = 0;  
            }
 
            int l = 1;
            while (l < k) {
                std::array<double, 10>
                    temp{};           
                double factor = NAN;  
                factor = projection(A[k - 1], B[l - 1], c);
                for (int i = 0; i < c; ++i) {
                    temp[i] = B[l - 1][i] * factor;  
                }
                for (int j = 0; j < c; ++j) {
                    all_projection[j] =
                        all_projection[j] +
                        temp[j];  
                }
                l++;
            }
            for (int i = 0; i < c; ++i) {
                B[k - 1][i] =
                    A[k - 1][i] -
                    all_projection[i];  
            }
        }
        k++;
    }
    display(r, c, B);  // for displaying orthogoanlised vectors
}

main()

int main

(

void

)

Main Function.

Returns

0 on exit

a 2-D array for storing all vectors

a 2-D array for storing orthogonalised vectors

storing vectors in array A

Input of vectors is taken

To check whether vectors are orthogonal or not

take make the process numerically stable, upper bound for the dot product take 0.1

Definition at line 248 of file gram_schmidt.cpp.

           {
    int r = 0, c = 0;
    test();  // perform self tests
    std::cout << "Enter the dimension of your vectors\n";
    std::cin >> c;
    std::cout << "Enter the number of vectors you will enter\n";
    std::cin >> r;
 
    std::array<std::array<double, 10>, 20>
        A{};  
    std::array<std::array<double, 10>, 20> B = {
        {0}};  
    for (int i = 0; i < r; ++i) {
        std::cout << "Enter vector " << i + 1
                  << '\n';  
        for (int j = 0; j < c; ++j) {
            std::cout << "Value " << j + 1 << "th of vector: ";
            std::cin >> A[i][j];
        }
        std::cout << '\n';
    }
 
    numerical_methods::gram_schmidt::gram_schmidt(r, c, A, B);
 
    double dot = 0;
    int flag = 1;  
    for (int i = 0; i < r - 1; ++i) {
        for (int j = i + 1; j < r; ++j) {
            dot = fabs(
                numerical_methods::gram_schmidt::dot_product(B[i], B[j], c));
            if (dot > 0.1)  
            {
                flag = 0;
                break;
            }
        }
    }
    if (flag == 0)
        std::cout << "Vectors are linearly dependent\n";
    return 0;
}

projection()

double numerical_methods::gram_schmidt::projection	(	const std::array< double, 10 > &	x,
		const std::array< double, 10 > &	y,
		const int &	c )

Projection Function Takes input of 2 vectors along with their dimension and evaluates their projection in temp

Parameters

x	Vector 1
y	Vector 2
c	dimension of each vector

Returns

factor

The dot product of two vectors is taken

The norm of the second vector is taken.

multiply that factor with every element in a 3rd vector, whose initial values are same as the 2nd vector.

Definition at line 79 of file gram_schmidt.cpp.

                                                               {
    double dot =
        dot_product(x, y, c);  
    double anorm =
        dot_product(y, y, c);  
    double factor =
        dot /
        anorm;  
    return factor;
}

test()

static void test ( )

static

Test Function. Process has been tested for 3 Sample Inputs

Returns

void

Definition at line 181 of file gram_schmidt.cpp.

                   {
    std::array<std::array<double, 10>, 20> a1 = {
        {{1, 0, 1, 0}, {1, 1, 1, 1}, {0, 1, 2, 1}}};
    std::array<std::array<double, 10>, 20> b1 = {{0}};
    double dot1 = 0;
    numerical_methods::gram_schmidt::gram_schmidt(3, 4, a1, b1);
    int flag = 1;
    for (int i = 0; i < 2; ++i) {
        for (int j = i + 1; j < 3; ++j) {
            dot1 = fabs(
                numerical_methods::gram_schmidt::dot_product(b1[i], b1[j], 4));
            if (dot1 > 0.1) {
                flag = 0;
                break;
            }
        }
    }
    if (flag == 0)
        std::cout << "Vectors are linearly dependent\n";
    assert(flag == 1);
    std::cout << "Passed Test Case 1\n ";
 
    std::array<std::array<double, 10>, 20> a2 = {{{3, 1}, {2, 2}}};
    std::array<std::array<double, 10>, 20> b2 = {{0}};
    double dot2 = 0;
    numerical_methods::gram_schmidt::gram_schmidt(2, 2, a2, b2);
    flag = 1;
    for (int i = 0; i < 1; ++i) {
        for (int j = i + 1; j < 2; ++j) {
            dot2 = fabs(
                numerical_methods::gram_schmidt::dot_product(b2[i], b2[j], 2));
            if (dot2 > 0.1) {
                flag = 0;
                break;
            }
        }
    }
    if (flag == 0)
        std::cout << "Vectors are linearly dependent\n";
    assert(flag == 1);
    std::cout << "Passed Test Case 2\n";
 
    std::array<std::array<double, 10>, 20> a3 = {{{1, 2, 2}, {-4, 3, 2}}};
    std::array<std::array<double, 10>, 20> b3 = {{0}};
    double dot3 = 0;
    numerical_methods::gram_schmidt::gram_schmidt(2, 3, a3, b3);
    flag = 1;
    for (int i = 0; i < 1; ++i) {
        for (int j = i + 1; j < 2; ++j) {
            dot3 = fabs(
                numerical_methods::gram_schmidt::dot_product(b3[i], b3[j], 3));
            if (dot3 > 0.1) {
                flag = 0;
                break;
            }
        }
    }
    if (flag == 0)
        std::cout << "Vectors are linearly dependent\n";
    assert(flag == 1);
    std::cout << "Passed Test Case 3\n";
}