MATLAB programming question: Write a function called that takes in one argument,

Question

MATLAB programming question:

Write a function called that takes in one argument, a matrix, performs gaussian elimination utilizing a partial pivoting strategy and elementary row operations only. Your function must not perform any permutations of the columns of the input matrix. Your function must return the the row echelon form of the input matrix. Before returning, your function must print the determinant of the input matrix. You may not use any of the following built in functions: det, lu, rref, qr, inv, rank, svd, sprank.

This question should be done in MATLAB code, however it's fine if you do this in JAVA, C, or C++

Explanation / Answer

Coding Hints

Your gaussian-elimination function should use secondary functions called by your main function as a structuring mechanism. A good place to start is to note that after the initial parameter checking, the process consists of two main steps. First, reduce the coefficient matrix to upper triangular form (modifying the constant vector in parallel). Second, perform the back-substitution to obtain the solution vector from the upper triangular matrix and the (modified) constant vector. We can write a secondary function to perform each step. Our main function thus starts out looking like this:

function solution_vec = gauss_reduce(param_mat, const_vec)

% check for consistent size of param_mat and const_vec

...

% reduce coefficient matrix to upper triangular form, modifying the

% constant vector appropriatly

[ut_mat, new_const_vec] = ut_reduce(param_mat, const_vec);

% Compute the solution vector using back substitution

solution_vec = back_subst(ut_mat, new_const_vec);

% we are done

end

The ut_reduce() function uses its own subsidiary functions. Specifically, you should write a function called reduce_column() with prototype

function [new_mat, new_const_vec] =

    reduce_column(param_mat, const_vec, column)

that returns a modified matrix (and constant vector) in which the input matrix has been reduced so that all the elements below the (col,col) diagonal element are zero. Initially it checks to see the (col, col) element is NOT zero, of course! This can be used iteratively to modify the original matrix and constant vector to produce an upper triangular form. Note that using a function to modify the matrix and vector passed as parameters in the following way,

[cur_mat, cur_vec] = reduce_column(cur_mat, cur_vec, cur_col);

is perfectly legitimate (as long as you don't need the old partial solutions) and a good way of structuring the process.

The reduce_column() function might itself call yet another function to reduce a specified column in a row to 0 by adding a multiple of another row, returning again, both a modified coefficient matrix and a modified constant vector. The prototype would look like

function [new_mat, new_const_vec] =

    reduce_row_at_col(param_mat, const_vec, ...

                      col, row_added, row_reduced);

This function adds a multiple of row_added to row_reduced so that the specified col in row_reduced is 0. The same operation is carried out on the corresponding position of the constant vector. (Basically like the "ERO" Attaway describes at the bottom of page 343)

The back-substitution function can similarly be constructed using a subsidiary function that takes the upper triangular matrix, the (modified) constant vector, and a partially-filled-in-from-the-end solution vector, (entries from col + 1 to the end already known) and produces a modified partial solution vector with entry col now filled in. The prototype would look like

function new_part_solution_vec =

    back_subst_for_col(ut__mat, new_const_vec,...

                        column, part_solution_vec)

****

Gaussian elimination is a method for solving matrix equations of the form

(1)

To perform Gaussian elimination starting with the system of equations

(2)

compose the "augmented matrix equation"

(3)

Here, the column vector in the variables  is carried along for labeling the matrix rows. Now, perform elementary row operations to put the augmented matrix into the upper triangular form

(4)

Solve the equation of the th row for , then substitute back into the equation of the st row to obtain a solution for , etc., according to the formula

(5)

In the Wolfram Language, RowReduce performs a version of Gaussian elimination, with the equation  being solved by

GaussianElimination[m_?MatrixQ, v_?VectorQ] :=

    Last /@ RowReduce[Flatten /@ Transpose[{m, v}]]

LU decomposition of a matrix is frequently used as part of a Gaussian elimination process for solving a matrix equation.

A matrix that has undergone Gaussian elimination is said to be in echelon form.

For example, consider the matrix equation

(6)

In augmented form, this becomes

(7)

Switching the first and third rows (without switching the elements in the right-hand column vector) gives

(8)

Subtracting 9 times the first row from the third row gives

(9)

Subtracting 4 times the first row from the second row gives

(10)

Finally, adding  times the second row to the third row gives

(11)

Restoring the transformed matrix equation gives

(12)

which can be solved immediately to give , back-substituting to obtain  (which actually follows trivially in this example), and then again back-substituting to find

(1)

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.