Week 6
Math505
Solution of Nonlinear Equations
with several variables: Fixed Point
method and Newton's method
Dr. BEDA T. ALETA
CILOs
C3. Solve numerical integration and differentiation
problems and recognize their application in computer
science and engineering problem solving.
C4. Analyze and solve mathematical problems using
various techniques for non-linear systems of
equations.
Week 4<Math505>: Solution of Nonlinear Equations with
several variables>
Outline
•Fixed-Point Iteration Successive Approximation
•Solution of System of Non-linear Equations with Several
Variables
Newton Raphson Method
Fixed Point Iteration
Fixed-Point Iteration-Successive
Approximation
• Many problems also take on the specialized
form: g(x)=x, where we seek, x, that satisfies
this equation. In the limit, f(xk)=0, hence xk+1=xk
Fixed-Point Iteration
• Rearrange the function f(x)=0 so that x is on the
left-hand side of the equation: x=g(x)
• Use the new function g to predict a new value
of x - that is, xi+1=g(xi)
• The approximate relative error is given by:
xi +1 − xi
εa = *100
xi +1
Examples
f ( x) = x 2 − x − 2 x>0
g ( x) = x 2 − 2
or
g ( x) = x + 2
or
2
g ( x) = 1 +
x
Condition for Convergence : g ′( x) < 1 for all x
Example 1:
Using fixed point iteration method find the root of
f(x) = e-x – x
1. Start with a guess say x1−=1,
xn +1 = e xn
2. Generate
a) x2=e-x1 = e-1= 0.368
b) x3=e-x2= e-0.368 = 0.692
c) x4=e-x3= e-0.692=0.500
In general:
After a few more iteration we will get 0.567 ≈ e −0.567
Example 2:
Use fixed point iteration to find the root of f ( x ) = 2 x 2 − 4 x + 1
• Find a root near x=1.0 and x=2.0
• Solution: x = g (x ) = x + 1
2
2 1
4
– Starting at x=1, x=0.292893 at 15th iteration
– Starting at x=2, it will not converge
– Why? Relate to g'(x)=x. for convergence g'(x) < 1
x = g (x ) = 2 x − 1 2
– Starting at x=1, x=1.707 at iteration 19
– Starting at x=2, x=1.707 at iteration 12
– Why? Relate to g ′(x ) = (2 x − 1 )− 1
2
2
Using fixed point iteration find the root of equation f(x) = 0, where
f(x) = x3 − 7x + 3
The rearrangement x = (x3 + 3)/7 leads to the iteration
xn + 3
3
xn +1 = , n = 0, 1, 2, 3, ...
7
To find the root , let initial approximation x0 = 2.
x0 + 3 23 + 3
3
x1 = = = 1.57143
7 7
x1 + 3 1.571433 + 3
3
x2 = = = 0.98292
7 7
x2 + 3 0.982923 + 3
3
x3 = = = 0.56423
7 7
x3 + 3 0.564233 + 3
3
x4 = = = 0.45423 etc.
7 7
The iteration slowly converges to give α = 0.441
Systems
Systems of
of Nonlinear Equations
Nonlinear Equations
•Locate the roots of a set of simultaneous nonlinear
equations:
f1 ( x1 , x2 , x3 , , xn ) = 0
f 2 ( x1 , x2 , x3 , , xn ) = 0
f n ( x1 , x2 , x3 , , xn ) = 0
Example:
x12 + x1 x2 = 10 ⇒ f1 ( x1 , x2 ) = x12 + x1 x2 − 10 = 0
x2 + 3 x1 x2 2 = 57 ⇒ f 2 ( x1 , x2 ) = x2 + 3 x1 x2 2 − 57 = 0
10
Newton’s Method for Systems of Non
Linear Equations
Given : X 0 an initial guess of the root of F ( x) = 0
Newton' s Iteration
X k +1 = X k − [F ' ( X k )] F ( X k )
−1
∂f1 ∂f1
∂x
f1 ( x1 , x2 ,...) ∂x2
1
∂f ∂f 2
F ( X ) = f 2 ( x1 , x2 ,...), F'(X ) = 2
∂x1 ∂x2
11
Example
• Solve the following system of equations:
y + x 2 − 0.5 − x = 0
x 2 − 5 xy − y = 0
Initial guess x = 1, y = 0
y + x 2 − 0.5 − x 2x −1 1 1
F = 2 , F ' = , X0 =
x − 5 xy − y 2 x − 5 y − 5 x − 1 0
12
Solution Using Newton’s Method
Iteration 1 :
y + x 2 − 0.5 − x − 0.5 2x −1 1 1 1
F = 2 = =, F ' = =
x − 5 xy − y 1 2 x − 5 y − 5 x − 1 2 − 6
−1
1 1 1 − 0.5 1.25
X1 = − 1 = 0.25
0 2 − 6
Iteration 2 :
0.0625 1.5 1
F = =, F ' =
- 0.25 1 . 25 − 7 . 25
−1
1.25 1.5 1 0.0625 1.2332
X2 = −
1.25 − 7.25 - 0.25 = 0.2126
0.25
13
Example
Try this
• Solve the following system of equations:
y + x2 −1− x = 0
x2 − 2 y2 − y = 0
Initial guess x = 0, y = 0
y + x 2 − 1 − x 2 x − 1 1 0
F = 2 , F ' = , X0 =
x − 2y − y
2
2x − 4 y − 1 0
14
Example
Solution
Iteration 0 1 2 3 4 5
_____________________________________________________________
0 − 1 − 0.6 − 0.5287 − 0.5257 − 0.5257
Xk 0 0 0.2 0.1969 0.1980 0.1980
15
FIXED POINT ITERATION METHOD FOR SYSTEM OF EQUATIONS
Using fixed point iteration method solve the system of equations.
Use the initial guess as x=1.5, y=3.5.
FIXED POINT ITERATION METHOD FOR SYSTEM OF EQUATIONS
After two iterations x=1.94053, y=3.04955
FIXED POINT ITERATION METHOD FOR SYSTEM OF EQUATIONS
Sufficient condition for convergence for two equations case are
These criteria are so restrictive that fixed-point iteration has limited
utility for solving nonlinear systems.
FIXED POINT ITERATION METHOD FOR SYSTEM OF EQUATIONS
Use fixed point iteration method to find the solution of
ex − y = 0
xy − e x = 0
inital approximation is y = 2.
The given system can be rearranged as
x = ln(y)
y=e /xx
FIXED POINT ITERATION METHOD FOR SYSTEM OF EQUATIONS
Iteration no y-value X-value
1 2 0.69315
2 2.88539 1.05966
3 2.72294 1.00171
4 2.71829 1.00000
5 2.71828 1.00000
FIXED POINT ITERATION METHOD FOR SYSTEM OF EQUATIONS
Use fixed point iteration method to find the solution of
x2 + y2 = 4
ex + y = 1
initial approximation is x = 1.
The given system can be rearranged as
y = - (4 - x 2 )
x = ln(1 − y )
FIXED POINT ITERATION METHOD FOR SYSTEM OF EQUATIONS
Iteration no x-value y-value
1 1.0051 -1.7291
2 1.00398 -1.72975
3 1.00421 -1.72961
4 1.00416 -1.72964
5 1.00417 -1.72963