ENGINEERING MATHEMATICS II
010.141
NUMERICAL METHODS IN
GENERAL
MODULE 5
NUMERICAL METHODS
Ø Methods for solving problems numerically on a computer Ø Steps:
• Modeling,
• Choice of a numerical method, Programming,
• Doing the computation,
• Interpreting the results
Ø Solution of equations by iteration Ø Interpolation
Ø Numerical integration and differentiation
B.D. Youn 3
2010 Engineering Mathematics II Module 5
Nonlinear Equations in Engineering Fields
f(x) = w
n(x) - w = 0
x: bridge design variables To design a safe bridge , a natural frequency must be higher than that of an external loading.
f(x) = T (x) - T* = 0
x: battery design variables To design a safe battery, a temperature level must be smaller than a marginal temperature.
f(x) = s (x) - S = 0
x: bridge gusset plate
To design a safe bridge,
a stress level at a critical
bridge element must be
smaller than its strength.
SOLUTION OF EQUATIONS BY ITERATION
Ø Solving equation f(x) = 0 Ø Methods:
• Fixed – Point Iteration
• Newton's Method
• Secant Method
B.D. Youn 5
2010 Engineering Mathematics II Module 5
FIXED-POINT ITERATION FOR SOLVING f(x) = 0
Ø Idea: transform f(x) = 0 into x = g(x)
Ø Steps:
1. Choose x 0
2. Compute x 1 = g(x 0 ), x 2 = g(x 1 ), ¼, x n+1 = g(x n )
Ø A solution of x = g(x) is called a fixed point
Ø Depending on the initial value chosen (x 0 ), the related
sequences may converge or diverge
FIXED-POINT ITERATION FOR SOLVING f(x) = 0
Ø Example: f(x) = x 2 – 3x + 1 = 0
î í
= ì
381966 .
0
618034 .
Solutions 2
B.D. Youn 7
2010 Engineering Mathematics II Module 5
FIXED-POINT ITERATION FOR SOLVING f(x) = 0
NEWTON'S METHOD FOR SOLVING f(x) = 0
Ø f must have a continuous derivative f ' Ø The method is simple and fast
( ) ( )
( ) ( ) 0
0 0 1
1 0
0 0
x ' f
x x f
x
x x
x x f
' f tan
-
=
ß
= -
=
b
B.D. Youn 9
2010 Engineering Mathematics II Module 5
NEWTON'S METHOD FOR SOLVING f(x) = 0
( ) ( )
( ) ( ) n
n n 1
n
1 1 1
2
x ' f
x x f
x
x ' f
x x f
x
-
=
-
=
+
M
NEWTON'S METHOD FOR SOLVING f(x) = 0
Example: Find the positive solution of f(x) = 2 sin x – x = 0
B.D. Youn 11
2010 Engineering Mathematics II Module 5
SECANT METHOD FOR SOLVING f(x) = 0
Newton’s method is powerful but disadvantageous because it
is difficult to obtain f '. The secant method approximates f '.
SECANT METHOD FOR SOLVING f(x) = 0
Ø Newton's Method
Ø Secant
B.D. Youn 13
2010 Engineering Mathematics II Module 5
SECANT METHOD FOR SOLVING f(x) = 0
진정성이 마음을 움직인다.
송나라 범관, 계산행려도
B.D. Youn 15
2010 Engineering Mathematics II Module 5
INTERPOLATION
Ø Function f(x) is unknown
Ø Some values of f(x) are known (f
1, f
2, ¼, f
n)
Ø Idea: Find a polynomial p
n(x) that is an approximation of f(x)
( ) 0 0 n ( ) 1 1 n ( ) n n
n x f , p x f , , p x f
p = = L =
Ø Lagrange interpolation
• Linear
• Quadratic
• General
Ø Newton's interpolation
• Divided difference
• Forward difference
• Backward difference
Ø Splines
LINEAR LAGRANGE INTERPOLATION
Ø Use 2 known values of f(x) ® f 0 , f 1
p 1 is the linear Lagrange polynomial.
B.D. Youn 17
2010 Engineering Mathematics II Module 5
LINEAR LAGRANGE INTERPOLATION
Ø p 1 (x) = L 0 (x)f 0 + L 1 (x)f 1
Ø L 0 and L 1 are linear polynomials (weight functions).
( ) ( )
ï î ï í ì
=
= ï =
î ï í ì
=
=
=
1 0 1
1 0
0 1 if x x
x x if 0 x
L x
x if 0
x x if 1 x
L
( ) ( )
0 1
0 1
1 0
1
0 x x
x x ,
x
x
-
= - -
= - x
x x L
x L
( ) 1
0 1
0 0
1 0
1
1 x x
x x
x
x x f
x f x
p -
+ - -
= -
LINEAR LAGRANGE INTERPOLATION
Example: Compute ln 9.2 from ln 9.0 = 2.1972 and ln 9.5 = 2.2513 by linear Lagrange interpolation
Solution:
( ) ( )
( )
( ) ( )
( ) ( )
2188 .
2
2513 .
2 4 . 0 1972
. 2 6 . 0
f 2 . 9 L f
2 . 9 L
2 . 9 p 2
. 9 ln
4 . 0 0
. 9 5 . 9
0 . 9 2 . 2 9
. 9 L 6
. 5 0
. 9 0 . 9
5 . 9 2 . 2 9
. 9 L
5 . 9 ln f
, 0 . 9 ln f
, 5 . 9 x
, 0 . 9 x
1 1
0 0
1
1 0
1 0
1 0
=
+
=
+
=
»
- =
= - - =
= -
=
=
=
=
B.D. Youn 19
2010 Engineering Mathematics II Module 5
QUADRATIC LAGRANGE INTERPOLATION
Ø Use of 3 known values of f(x) ® f 0 , f 1 , f 2
Ø Approximation of f(x) by a second-degree polynomial
( ) ( ) ( ) ( )
( )( )
( )( )
( )( )
( )( )
( )( )
( 2 0 )( 2 1 )
1 2 0
2 1
0 1
2 1 0
2 0
1 0
2 0 1
2 2
1 1
0 0
2
x x
x x
x x
x L x
x x
x x
x x
x L x
x x
x x
x x
x L x
f x L f
x L f
x L x
p
- -
-
= -
- -
-
= -
- -
-
= -
+ +
=
QUADRATIC LAGRANGE INTERPOLATION
Example: Compute ln 9.2 for f
0(x
0= 9.0) = ln 9.0, f
1(x
1= 9.5) = ln 9.5, f
2(x
2= 11.0) = ln 11.0
Solution:
( )
( ) ( )
( ) ( )
( 9 . 2 ) 2 . 2192
2 . 9 ln
5 . 85 5
. 3 18
1
99 75 20
. 0
1
5 . 104 5
. 20
2 2 2
2 1
2 0
=
»
+ -
=
+ -
-
=
+ -
=
p
x x
x L
x x
x L
x x
x
L
B.D. Youn 21
2010 Engineering Mathematics II Module 5
GENERAL LAGRANGE INTERPOLATION
( ) ( ) ( )
( ) ( )
( ) ( ) ( k )( k ) ( n )
k n
k n
k n
x x x
x x
x x
x x
l
x f l
x l
f x x
p x
f
- -
- -
=
=
=
»
+ -
=
=
å å
L
L 1 1
0 k
0 k k
k 0 k
k
L
NEWTON'S INTERPOLATION
Ø More appropiate for computation
Ø Level of accuracy can be easily improved by adding new terms that increase the degree of the polynomial Ø Divided difference
Ø Forward difference
Ø Backward difference
B.D. Youn 23
2010 Engineering Mathematics II Module 5
Is High-Order Polynomial a Good Idea?
f(x) = 1/(1+25x^2)
Ø Method of interpolation used to avoid numerical instability
Ø Idea: given an interval [a, b] where the high-degree polynomial can oscillate considerable, we subdivide [a, b] in several smaller intervals and use several low-degree polynomials (which cannot oscillate much)
SPLINES
B.D. Youn 25
2010 Engineering Mathematics II Module 5
SPLINES (cont)
Ø In an interval x Î [x
j, x
j+1], j = 0 , ¼, n – 1
where
( ) j j ( j ) j ( j ) 2 j ( j ) 3
j x a a x x a x x a x x
p =
0+
1- +
2- +
3-
( ) ( )
(
j j) (
j j)
j
j j
j j
j j j
j j
j j
j j
j j
k h k
f h f
a
k h k
f h f
x p a
k x
p a
f x
p a
+ +
-
=
+ -
-
¢¢ =
=
¢ =
=
=
=
+ +
+ +
2 1 3 1
3
1 2 1
2 1 0
1 2
1 2 ) 3
2 ( 1
) (
)
(
SPLINES (cont)
Ø Let (x 0 ,f 0 ), (x 1 ,f 1 ), … , (x n ,f n ).
Ø k 0 , k n are two given numbers.
Ø k 1 , k 2 , ¼, k n-1 are determined by a linear system of n-1 equations:
Ø h is the distance between nodes x n = x 0 + nh
( )
( ) , ' ( 1 ) ( j 0, 1, , n - 1 )
'
4 3
1 1 1
1 1
= K
= +
=
-
= +
+
+ - +
+ -
j j
j j
j j
j j
j j
j
k x
p k
x p
f h f
k k
k
B.D. Youn 27
2010 Engineering Mathematics II Module 5
SPLINES (cont)
Ø Clamped conditions
g'(x 0 ) = f'(x 0 ), g'(x n ) = f'(x n )
Ø Free/natural conditions
g"(x 0 ) = 0, g"(x n ) = 0
Ø Example:
Interpolate f(x) = x 4 on interval x Î [-1, 1] by cubic spline in partitions x 0 = -1, x 1 = 0, x 2 = 1, satisfying clamped conditions
g'(-1) = f'(-1), g'(1) = f'(1)
SPLINES (cont)
B.D. Youn 29
2010 Engineering Mathematics II Module 5
SPLINES (cont)
NUMERICAL INTEGRATION
Ø Numerical evaluation of integrals whose analytical evaluation is too complicated or impossible, or that are given by recorded numerical values
Ø Rectangular rule Ø Trapezoidal rule Ø Simpson's rule
ò ( )
b
a
dx
x
f
B.D. Youn 31
2010 Engineering Mathematics II Module 5
RECTANGULAR RULE
Ø Approximation by n rectangular areas
where
h x
x
n a h b
0
1 = +
= -
( ) [ ( ) ( ) ( n ) ]
b
a
x f x
f x
f h dx
x f
J = ò » * 1 + * 2 + L + *
TRAPEZOIDAL RULE
Ø Approximation by n trapezoidal areas
( ) ( ) ( ) ( ) ( ) ( ) ú
û ù ê ë
é + + + + +
»
= ò f x dx h f a f x f x f x - f b
J n
b
a 2
1 2
1
1 2
1 L
B.D. Youn 33
2010 Engineering Mathematics II Module 5
TRAPEZOIDAL RULE
SIMPSON'S RULE
Ø Approximation by parabolas using Lagrange polynomials p
2(x)
Ø Interval of integration [a, b] divided into an even number of subintervals
( )
( ) ( )
( )
j jm m
m b
a
x f f
f f
f f
f f
h f dx
x f
h x
h a x
m f a h b
=
+ +
+ +
+ +
+
»
+
= +
= - =
=
-
ò
0 1 2 3 2 -2 2 1 21 2
1 0
0
4 2
4 2
3 4
x x
f 2
L
B.D. Youn 35
2010 Engineering Mathematics II Module 5
SIMPSON'S RULE
SIMPSON'S RULE
B.D. Youn 37
2010 Engineering Mathematics II Module 5
