We will study a direct method for solving linear systems: the Cholesky decomposition. Given a symmetric positive definite matrix A, the aim is to build a lower triangular matrix L which has the following property: the product of L and its transpose is equal to A.




Given a symmetric positive definite matrix , the Cholesky decomposition constructs a lower triangular matrix L which has the following property: . A symmetric matrix is positive definite if, for any vector , the product is positive.

The matrix is sometimes called the « square root » of . The Cholesky decomposition is often used to calculate the inverse matrix and the determinant of (equal to the square of the product of the diagonal elements of ).



But as always it is important to learn doing an example, so here it is

Example

If a matrix is defined as


Then the LU factorization can be shown as:



Factoring out the diagonal elements in:



Performing the Cholesky descomposition yields:



Then, verifying the results



So that is it

False position is a very interesting method and is commonly used when other methods does not converge.



Here, we start with an initial interval [x1,x2], and we assume that the function changes sign only once in this interval. Now we find an x3 in this interval, which is given by the intersection of the x axis and the straight line passing through (x1,f(x1)) and (x2,f(x2)). It is easy to verify that x3 is given by



Now, we choose the new interval from the two choices [x1,x3] or [x3,x2] depending on in which interval the function changes sign.

The false position method differs from the bisection method only in the choice it makes for subdividing the interval at each iteration. It converges faster to the root because it is an algorithm which uses appropriate weighting of the intial end points x1 and x2 using the information about the function, or the data of the problem. In other words, finding x3 is a static procedure in the case of the bisection method since for a given x1 and x2, it gives identical x3, no matter what the function we wish to solve. On the other hand, the false position method uses the information about the function to arrive at x3.

But for a better learning here is an example, i hope you enjoy it.

Example
FInd the root of the equation X2+X-1=0, with a=0 and b=1, using the false position method.

It is easy to verify that f(x)=X2+X- 1 and f"(x)=2. Since f(1)>0 and and f"(1)>0, therefor Xo=0 and b=1.

so

For n=0 we have:


For n=1 we have:


For n=2 we have:


For n=3 we have:


For n=4 we have:


For n=5 we have:


the required root of the equation X2+X- 1=0 is =0.618.

Now i have a new topic to talk about and its Gauss-Seidel method, i find it very interesting so im going to explain it here.



After reading this, you should be able to:

1. solve a set of equations using the Gauss-Seidel method,
2. recognize the advantages and pitfalls of the Gauss-Seidel method, and
3. determine under what conditions the Gauss-Seidel method always converges.




Why do we need another method to solve a set of simultaneous linear equations?

In certain cases, such as when a system of equations is large, iterative methods of solving equations are more advantageous. Elimination methods, such as Gaussian elimination, are prone to large round-off errors for a large set of equations. Iterative methods, such as the Gauss-Seidel method, give the user control of the round-off error. Also, if the physics of the problem are well known, initial guesses needed in iterative methods can be made more judiciously leading to faster convergence.
What is the algorithm for the Gauss-Seidel method? Given a general set of equations and unknowns, we have



If the diagonal elements are non-zero, each equation is rewritten for the corresponding unknown, that is, the first equation is rewritten with on the left hand side, the second equation is rewritten with on the left hand side and so on as follows



so




As i always say, it is important to make an example so the concepts get clear, and here it is:

Example
Find the solution to the following system of equations using the Gauss-Seidel method.



Use



as the initial guess and conduct two iterations.

Solution

The coefficient matrix



is diagonally dominant an the inequality is strictly greater than for at least one row. Hence, the solution should converge using the Gauss-Seidel method.
Rewriting the equations, we get



Iteration #1



The absolute relative approximate error at the end of the first iteration is



Iteration #2



At the end of second iteration, the absolute relative approximate error is:





This is close to the exact solution vector of

A interesting iteration method that i have been searching is the Bairstow Method, which is based in the Müllers and the Newton-Raphson method.

It is very important because it allows to calculate all the polinomic roots, no matter if they are real or imaginary.



Here there are some steps that may help you to solve polynomials with this accurate method, i hope you enjoy learning this:

With a polinomyal like fn(x)you must find two factors, a cuadratic polynomial f2(x) = x2 – rx – s and fn-2(x)
.

This is the general procedure for Bairstow Method:

1.) With fn(x) and r0 and s0.

2.) With the Newton-Raphson method you calculate f2(x) = x2 – r0x – s0 and fn-2(x).

3.) You determine the roots f2(x) using the general formula.

4.) You calculate fn-2(x)= fn(x)/ f2(x)..

5.) Then you equal fn(x)= fn-2(x).

6.) If the grade of the polinomyal is greater than three, you must go back to step two.

7.) If no, you have sucesfully iterate a polynomial with Bairstows Method.

But as always we only learn making an example, so here it is.

EXAMPLE:

With the polynomial f5(x) = x5 - 3.5x4 + 2.75x3 + 2.125x2 - 3.875x + 1.25, determine the r and s values who make the equation equal to zero. Consider r0 = -1 y s0 = 2.
First iteration.

The syntethic division with the polynomial f2(x) = x2 -x + 2.0 takes as result:

f3(x) = x3 - 4.5x2 + 9.25x - 16.125 Residue = {30.75, -61.75}

Applying the Newton method we have:

-43.875.......16.75......dr.....-30.75

108.125.......-43.87.....ds.....61.75


r1 = -1.0 + 2.7636812508572213 =1.7636812508572213

s1 = 2.0 + 5.403374022767796 =7.403374022767796

Second iteration.

The syntethic division with the polynomial f2(x) = x2 -1.7636812508572213x - 7.403374022767796 giva as result:

f3(x) = x3 - 1.7363187491427787x2 + 7.091061199392814x - 1.776754563401905

Residue = {51.75640698828836, 105.68578319650365}

Applying the Newton method we have:



27.628006.......14.542693.......dr.........-51.75640

208.148405......27.62800........ds.........-105.68578


From were

r2 = 1.7636812508572213 - 0.04728019113442016 = 1.7164010597228012

s2 = 7.403374022767796 - 3.469106187802152 = 3.934267834965644
The syntethic division with the polynomial f2(x)= x2 - 1.7164010597228012x - 3.934267834965644 give as result:

f3(x) = x3 - 1.7835989402771988x2 + 3.622896723753395x + 1.3261878347051992

Residue = {12.654716254544885, 28.1881465309956}

Applying the Newton method we have:



13.83497........7.44188.........dr........-12.65471

65.679212.......13.83497........ds........-28.18814



From were

r3 = 1.7164010597228012 - 0.11666951305731528 = 1.599731546665486

s3 = 3.934267834965644 - 1.4835870659929915 = 2.4506807689726524

In brief

k..................r...............s.....................Residuo

0.................-1...............2..................30.75......-61.75

1...............1.76368.........7.403374............51.75640.....105.68578

2...............1.71640.........3.93426.............12.65471.....28.18814

3...............1.599731........2.450680............2.89958......8.1546

4...............1.33354.........2.18666.............0.760122.....2.522228

5...............1.11826.........2.113020............0.271940.....0.607688

6...............1.02705.........2.02317.............0.04313......0.11185

7...............1.00165.........2.00153.............0.00277......0.00634

8...............1.00000.........2.00000.............1.13930E-5...2.67534E-5

The solution is:

f3(x) = x3 - 2.53x2 + 2.25x - 0.625 y f2(x) = x2 - x - 2

The roots of f2(x) = x2 - x - 2, are

x1 = 2

x2 = -1