PS 11:
NUMERICAL METHODS
NUMERICAL ERRORS
- The difference between an exact mathematical value (true value) and the approximate
value obtained through a numerical method or computation.
ROUND - OFF ERRORS
- Arises from the inability of digital computers to represent real numbers exactly. Due to
finite number of bits available for storage, numbers are often rounded or "chopped" to a
certain number of significant digits or decimal places.
TRUNCATION ERRORS
- Occur when an exact methematical procedure or infinite process is approximately by a
finite one.
ABSOLUTE ERROR, Ea
- How far a measurement is from the actual or true value
RELATIVE ERROR, Er
- Ratio of absolute error to the true or exact value.
PERCENTAGE ERROR, Ep
- Expressing the error as a percentage of true or exact value.
TYPE OF EQUATIONS
ALGEBRAIC EQUATION
- An equation of type y=f(x) that can be expressed in the form:
Examples:
POLYNIMIAL EQUATIONS
- A simple class of algebraic equation that represented as follows
Where: n is the degree of polynomial ( has n roots)
Examples:
TRANSCENDENTAL EQUATIONS
- non algebraic equations that may include trigonometric, exponential, and logarithmic
functions.
Examples:
ITERATIVE METHOD
- Computational technique that generates a sequence of improving approximate solutions
to a mathematical problem, starting form initial guess (X0).
- The output of each step becomes our input for the next step.
2 Case may arise from initial guess:
1. Convergent
- Will approach to the actual X value or root.
2. Divergent
- Will not approach to the actual X value or root.
THREE MAJOR COMPONETS OF ITERATIVE METHOD
1. Iterative (recursive) Formula
2. Initial Guess (X0)
3. Terminating Condition - this is when to stop the iteration.
a. When the computed value is the actual root, then stop.
b. If there is a specified number of iterations in the problem.
c. Error tolerance. ( Current - Previous )
NUMERICAL METHODS BY THEIR INITIAL
APPROXIMATION OR WHAT WE CALL INITIAL GUESS
BRACKETING METHODS
- Methods that uses two initial guesses/approximation for the root.
- The actual value of X or the root must be between the two initial guesses or interval.
[ X0, X1]
With the two initial guesses X0 and X1, there follow corresponding f(X0) and f(X1)
Where: f(X0) * f(X1) < 0
These methods includes: a) Bisection Method, b) Regula Falsi Method
OPEN METHODS
- Methods that may used one (1) or two (2) initial guesses or approximation.
- For 2 initial guesses, unlike bracketing the actual root is NOT required to be between the
initial guesses.
Since these methods do not have bracketing property, the consequence is that they do
not always converge. But when they do, they converge faster than bracketing techniques.
These methods includes: a) Secant Method, b) Newton - Raphson Method,
c)Fixed - point Iteration.
NUMERICAL SOLUTION TO LINEAR AND NONLINEAR ALGEBRAIC EQUATIONS
BISECTION/ INTERVAL - HALVING METHOD
- Root finding method, provided that the roots lie within the interval [Xn, Xp] and f(x) is
continuous in the interval.
- Closed bracket type, requiring two initial guesses.
- Convergence is linear. Applicable to Linear and Transcendental equations.
- Convergence is relatively slow compared to other rooting finding methods because of
its slow and steady rate of convergence.
INTERVAL
STEP # 1
- IDENTIFY Xn AND Xp IN THE GIVEN INTERVAL.
STEP # 2
Where: Xn - X value where f(Xn) is NEGATIVE
Xp - X value where f(Xp) is POSITIVE
Xo - Midpoint of the interval.
STEP # 3
- Evaluate f(x) at Xo (f(Xo))
THREE CASES MAY ARISE AT f(Xo)
a) f(Xo) = 0: Xo is the required ROOT of the equation.
b) f(Xo) > 0: The root lies in the interval [Xn, Xo]
c) f(Xo) < 0: The root lies in the interval [Xo, Xp]
STEP # 4
- The iteration is repeated by updating values of Xn and Xp until termination condition is
satisfied. Its Either Xn will remain or Xp.
CALTECH FOR BISECTION/HALVING METHOD
AFTER IDENTIFYING YOUR Xn AND Xp
FIRST ITERATION
NEXT ITERATION
FALSE POSITION/ REGULA FALSI METHOD
- Similar to bisection except that the next iterate is taken at the intersection of a line
between the pair of x-values and the x-axis .
- Faster convergence than Bisection. Also, applicable to both polynomial and
transcendant equations for root finding.
- Also known as LINEAR INTERPOLATION or METHOD OF FALSE POSITION.
Given pair of x values [Xk-1 , X k ]
X k-1= Xn
X k = Xp WHERE: k - is the number of iteration
STEP # 1
- Identify your X k-1 and X k , then solve f(X k-1) and f(X k )
STEP # 2
- Find X k+1
STEP # 3
- Solve f(X k+1)
STEP # 4
- Determine the sign of f(X k+1), next new pair of points in which the next iterate will be found:
f(X k+1) >0: [( X k-1, f(X k-1 ) ), ( X k+1, f(X k+1) )]
f(X k+1) <0: [( Xk+1 , f(Xk+1) ), ( X k , f(X k ) )]
STEP # 5
- Repeat from step 2, until terminating condition is satisfied.
CALTECH FOR FALSE POSITION METHOD
k=1; FIRST ITERATION
k>1; NEXT ITERATIONS
SECANT METHOD
- Root finding algorith that uses a succession of roots of secant line.
- Closely related with false position method.
The secant method differs from the false position method in two details:
1. It does not require prior bracketing of the roots; and
2. The oldest prio estimate of the root is discarded (X k-1 ) after Xk+1 is computed.
- If the function is far from linear near root, the successive iterates can fly off to points
far from the root.
STEP # 1
- Solve f(X k-1) and f(X k )
STEP # 2
- Find X k+1
STEP # 3
- Set new interval [ X k ,X k+1 ], discard the oldest prio estimate of the root (X k-1 )
STEP # 4
- Repeat from step # 1 for the following next iteration until terminating condition is satisfied
CALTECH FOR SECANT METHOD
k=1; FIRST ITERATION
k>1; NEXT ITERATIONS
NEWTON - RAPHSON METHOD
- Named after Isaac Newton and Joseph Raphson
- is a root-finding algorithm, and its convergence is quadratic.
- Root is not bracketed.
- Only one initial guess of the root is needed.
- Drawback of the method is that it uses derivative f '(x), therefore this method is usable
only in problems where derivative of f(x) can be readily computed.
STEP # 1
- Solve f '(x)
STEP # 2
- Solve f(Xk) and f ' (Xk)
STEP # 3
- Find X k+1
STEP # 4
- Repeat from step # 2 to step # 3 until the root within desirable tolerance is found or the
terminating condition is satisfied.
CALTECH FOR NEWTON - RAPHSON METHOD
k=1, FIRST ITERATION
K>1, NEXT ITERATIONS
FIXED - POINT ITERATION METHOD
- Also known as x=g(x) method.
- Applicable to both polynomial and transcedental equations.
STEP # 1
- Re-arrange f(x) = 0 into an equivalent form x= g(x), which usually can be done in several
ways.
STEP # 2
- Since g(x) is not unique, not all of them will converge for a given initial value (X0)
- Step # 2 is to test for convergence.
Condition for convergence is:
STEP # 3
STEP # 4
- Repeat step # 3 until find the fixed point (root) or until terminating condition is satisfied.
CALTECH FOR FIXED - POINT ITERATION METHOD
AFTER TESTING FOR CONVERGENCE
k = 1, FIRST ITERATION
k>1, NEXT ITERATIONS
LU FACTORIZATION METHODS (LU DECOMPOSITION )
- " Direct method " for solving systems of (simultaneous) linear algebraic equations
Computing a solution with a finite number of steps.
- The original matrix A (from simultaneous equations) is decomposed into lower and upper
triangular matrices.
* for a set of linear equations Ax = b we express the coefficient matrix A as the product
(left side variable terms) (right side constant terms)
of lower of a lower triangular matrix L and upper triangular matrix U do that the form Ax = b
becomes LUx = b
* Solving simplified matrices by forward and backward substitution process, Ly = b,
finally Ux = y
Step # 1 Write the system into the form Ax = b
Step # 2 Decomposed A into L and U
Step # 3 Solve for y from Ly = b
Step # 4 Finally, solve for x from Ux = y
LU FACTORIZATION BY DOOLITTLE'S METHOD
- Decompose matrix A into L and U such that L will have 1's on the main diagonal
- From the simultaneous equations, get coefficients, then rewrite in the form matrix A.
This is matrix A, came from Lower triangular matrix Upper triangular matrix
coefficients of simultaneous NOTE! Subscript are always ROW by COLUMN
equations.
Applying the multiplication of Matrices!
(anm) = (coefficients in row n) x ( coefficients in column m)
FOR DOOLITTLE ( Find the first row of upper matrix U first)
FOR FIRST ROW OF MATRIX U
FOR FIRST COLUMN OF MATRIX L
FOR i = 2, 3, . . . , n
ROW ELEMENT OF MATRIX U
COLUMN ELEMENT OF MATRIX L
LU FACTORIZATION BY CROUT'S METHOD
- Decompose matrix A into L and U such that U will have 1's on the main diagonal
- From the simultaneous equations, get coefficients, then rewrite in the form matrix A.
This is matrix A, came from Lower triangular matrix Upper triangular matrix
coefficients of simultaneous NOTE! Subscript are always ROW by COLUMN
equations.
Applying the multiplication of Matrices!
(anm) = (coefficients in row n) x ( coefficients in column m)
FOR CROUT'S ( Find the first column of lower matrix L first)
FOR FIRST COLUMN OF MATRIX L
FOR FIRST ROW OF MATRIX U
FOR j = 2, 3, . . . , n
COLUMN ELEMENT OF MATRIX L
ROW ELEMENT OF MATRIX U
LU FACTORIZATION BY CHOLESKY'S METHOD
- Does not have any condition for main fiagonal entries
- Limitations: coefficient matrix A, must be sysmmetric and positive definite.
Conditions for a positive definite matrix
a) Symmetric and all eigenvalues are positive.
b) Symmetric and all pivots are positive.
c) Symmetric and all upper left k x k determinants are positive .
For a symmetric, positive definite marix A,
(Transposition of matrix)
HENCE
* Then proceed with multiplication of matrix ( starting w/ 1st column of A)
LIMITATIONS OF CHOLESKY DECOMPOSITION A = L L
1) Cholesky's method can only be applied to symmetric matrices.
2) The decomposition process involves taking square roots of certain combinations of the
elements of matrix A. Square root of a negative number can be avoided only if matrix A
is positive definite.
FOR FIRST COLUMN
FOR j = 2,3,...,n
ITERATIVE METHODS IN SOLVING SIMULTANEOUS EQUATIONS
- Advantage when systems of equation is large the coefficient matrix is sparse (has many
zeros)
- Can also be applied to sets of nonlinear equations.
- Starts w/ an initial guess of the solution ( usually zero) then repeatedly improve the solution
until " change from previous to next value" is negligible.
- The convergence is guaranteed only if the coefficient matrix is diagonally dominant.
- For hand computation, they have the distinct advantage that they are self - correcting
if an error is made.
JACOBI METHOD
- Method of simultaeneos displacement.
- Each of the equation is simultaeneously changed using the most recent set of values
STEP # 1
- Arrange coeffecient matrix which is diagonally dominant.
STEP # 2
Where: - New estimate for the variable
- Previous estimate for the variable
STEP # 3
- Start iteration, repeat until terminating condition is satisfied. For initial condition if no
better initial estimates are at hand use 0 but it must be stated in the problem.
CALTECH FOR JACOBI METHOD
AFTER DOING STEP 1 AND STEP 2
k=1, FIRST ITERATION
k>1, NEXT ITERATIONS
GAUSS - SIEDEL METHOD
- A varient of the jacobi method.
- Improve convergence from jacobi method.
- After solving one value, this latest available value will be used immediately fo the next
solution.
STEP # 1
- Arrange coeffecient matrix which is diagonally dominant.
STEP # 2
Where: - New estimate for the variable
- Previous estimate for the variable
STEP # 3
- Start iteration, repeat until terminating condition is satisfied. For initial condition if no
better initial estimates are at hand use 0 but it must be stated in the problem.
CALTECH FOR GAUSS - SIEDEL METHOD
AFTER DOING STEP 1 AND 2
k=1, FIRST ITERATION
k>1, NEXT ITERATIONS
KRON'S REDUCTION