NONLINEAR
Bisection Method
Example: f(x) = x^3+x^2-3x-3=0
starting values: a=1, b=2
tolerance: 0.0001
f(x) 1 1 -3 -3
ITERATION: x1 x2 f(x1) f(x3) f(x1)*f(x3) x3=(x1+x2)/2 F(x3)=tolerance
1 1.000000 2.000000 -4.000000 -1.875000 7.500000 1.500000 -1.875000
2 1.500000 2.000000 -1.875000 0.171875 -0.322266 1.750000 0.171875
3 1.500000 1.750000 -1.875000 -0.943359 1.768799 1.625000 -0.943359
4 1.625000 1.750000 -0.943359 -0.409424 0.386234 1.687500 -0.409424
5 1.687500 1.750000 -0.409424 -0.124786 0.051091 1.718750 -0.124786
6 1.718750 1.750000 -0.124786 0.022030 -0.002749 1.734375 0.022030
7 1.718750 1.734375 -0.124786 -0.051755 0.006458 1.726563 -0.051755
8 1.726563 1.734375 -0.051755 -0.014957 0.000774 1.730469 -0.014957
9 1.730469 1.734375 -0.014957 0.003513 -0.000053 1.732422 0.003513
10 1.730469 1.732422 -0.014957 -0.005728 0.000086 1.731445 -0.005728
11 1.731445 1.732422 -0.005728 -0.001109 0.000006 1.731934 -0.001109
12 1.731934 1.732422 -0.001109 0.001201 -0.000001 1.732178 0.001201
13 1.731934 1.732178 1.732056 0.000046
Algorithm:Set x3 = (x1+x2)/2, If f(x3)*f(x1) < 0 then x2 = x3. Otherwise, x1= x3.
Nonpolynomial: Newton's Method
f ( xn )
x n+1 =x n , n=0,1,2, . ..
Ex. f(x)= 3x + sinx -e^x = 0 f ' ( xn )
find: the root of f(x)
f'(x) = 3 +cosx - e^x tolerance
x sinx cosx e^x f(xi) f'(xi)
x0= 0 0 1 1 -1 3
x1= 0.333333 0.3271947 0.9449569 1.39561243 -0.068417728 2.5493445212
x2= 0.360171 0.352434 0.9358367 1.43357412 -0.000627985 2.5022625478
x3= 0.360422 0.3526689 0.9357482 1.43393395 -5.6252E-008
Exercise: 1. Use bisection method to find a root of f(x)=x^3 -3x^2-6x+8=0 near x=3.5
2. Use Newton's method to finf the root of f(x) = e^x -4x^2, near x= 0.7.
Interpolation: Divided difference
Example:
xi f(xi)=fi[0] fi[1] fi[2] fi[3] fi[4]
3.200 22.000
2.700 17.800 8.400
1.000 14.200 2.118 2.856
4.800 38.300 6.342 2.012 -0.527
5.600 51.700 16.750 2.263 0.087 0.256
Pn ( x )=f [ 0] +(x x0 ) f [1] +( x x0 )( xx 1 )f [2 ] +.. .+( xx 0 )(x x1 ). ..( x xn1 )f [n ]
0 0 0 0
P4(x)= 22.000+8.4(x-3.2)+2.856(x-3.2)(x-2.7)-0.527(x-3.2)(x-2.7)(x-1)+0.256(x-3.2)(x-2.7)(x-1)(x-4.8)
Least Squares Approximation: y = ax + b
Normal Eqns: a x 2
i
+ b xi = xi Y i
a xi + bN = Yi
Example:
x=T,0C y=R,
ohms x^2 xy
1 20.5 765 420.25 15682.5
2 32.7 826 1069.29 27010.2
3 51 873 2601 44523
4 73.2 942 5358.24 68954.4
5 95.7 1032 9158.49 98762.4
SUM 273.1 4438 18607.27 254932.5
N= 5
xi 273.1 xi Y i 254932.5
x i2 18607.27 Yi 4438
a b k
18607.27 273.1 254932.5
273.1 5 4438 X=[a,b]^T
AX= K
inv(A)= 0.000271 -0.0148 AX=K X=inv(A)*K
-0.0148 1.008374
a= 3.394873 y=ax+b R=aT+b
b= 702.1721
Thus, R = 702.2 + 3.39T. T=(R-702.2)/3.39
at T=100 R= 1041.659
at T=50 R= 871.9157
at R=900 ohms T= 58.272567
Exercise 4 3) Construct a divided difference table from these data.
x f(x)
0.5 1.0025
-0.2 1.394
0.7 1.0084
0.1 1.1221
Obtain the 3rd degree interpolating polynomial.
What is the value of f(x) at x = 0.3?
4)Find the least squares line that fits the following data. Find f(18.4).
x f(x)
1 5.04
2 8.12
3 10.64
4 13.18
5 16.2
6 20.04
Then find the value of f(x) at x = 10.5.
.( x xn1 )f [n ]
0
7)(x-1)(x-4.8)
xi [0] f(xi)=fi[0] [1] fi[1] [2] fi[2] [3] fi[3]
x0 3.200 f0 22.000
x1 2.700 f1 17.800 f0 8.400
x2 1.000 f2 14.200 f1 2.118 f0 2.856
x3 4.800 f3 38.300 f2 6.342 f1 2.012 f0 -0.527
x4 5.600 f4 51.700 f3 16.750 f2 2.263 f1 0.087
P4(x)= 22.000+8.4(x-3.2)+2.856(x-3.2)(x-2.7)-0.527(x-3.2)(x-2.7)(x-1)+0.256(x-3.2)(x-2.7)(x-1)(x-4.8)
P(x=1.5) = 12.14627 ans.
x= 1.5
[4] fi[4]
f0 0.256 `````````
ans
Table 1 Table 2
delta x = 0.1 delta x = 0.05
x y y^2 x^2 dy x y y^2
0.000 1.000 1.000 0.000 0.100 0.000 1.000 1.000
0.100 1.100 1.210 0.010 0.120 0.050 1.050 1.103
0.200 1.220 1.488 0.040 0.145 0.100 1.105 1.221
0.300 1.365 1.863 0.090 0.177 0.150 1.166 1.359
0.400 1.542 2.378 0.160 0.222 0.200 1.232 1.519
0.500 1.764 3.111 0.250 0.286 0.250 1.306 1.706
0.300 1.388 1.928
Table 3 0.350 1.480 2.192
delta x = 0.01 0.400 1.584 2.509
x y y^2 x^2 dy 0.450 1.701 2.894
0.000 1.000 1.000 0.000 0.010 0.500 1.836 3.370
0.010 1.010 1.020 0.000 0.010
0.020 1.020 1.041 0.000 0.010
0.030 1.031 1.062 0.001 0.011
0.040 1.041 1.084 0.002 0.011
0.050 1.052 1.107 0.003 0.011
0.060 1.063 1.130 0.004 0.011
0.070 1.074 1.154 0.005 0.011
0.080 1.086 1.179 0.006 0.012
0.090 1.098 1.205 0.008 0.012
0.100 1.110 1.231 0.010 0.012
0.110 1.122 1.258 0.012 0.012
0.120 1.134 1.286 0.014 0.013
0.130 1.147 1.315 0.017 0.013
0.140 1.160 1.345 0.020 0.013
0.150 1.173 1.376 0.023 0.014
0.160 1.187 1.408 0.026 0.014
0.170 1.201 1.441 0.029 0.014
0.180 1.215 1.475 0.032 0.014
0.190 1.229 1.511 0.036 0.015
0.200 1.244 1.547 0.040 0.015
0.210 1.259 1.585 0.044 0.015
0.220 1.274 1.624 0.048 0.016
0.230 1.290 1.664 0.053 0.016
0.240 1.306 1.706 0.058 0.016
0.250 1.323 1.749 0.063 0.017
0.260 1.340 1.794 0.068 0.017
0.270 1.357 1.841 0.073 0.018
0.280 1.374 1.889 0.078 0.018
0.290 1.393 1.939 0.084 0.019
0.300 1.411 1.991 0.090 0.019
0.310 1.430 2.045 0.096 0.019
0.320 1.450 2.101 0.102 0.020
0.330 1.470 2.160 0.109 0.021
0.340 1.490 2.221 0.116 0.021
0.350 1.511 2.284 0.123 0.022
0.360 1.533 2.350 0.130 0.022
0.370 1.555 2.418 0.137 0.023
0.380 1.578 2.490 0.144 0.023
0.390 1.601 2.564 0.152 0.024
0.400 1.625 2.642 0.160 0.025
0.410 1.650 2.723 0.168 0.026
0.420 1.676 2.808 0.176 0.026
0.430 1.702 2.897 0.185 0.027
0.440 1.729 2.990 0.194 0.028
0.450 1.757 3.088 0.203 0.029
0.460 1.786 3.190 0.212 0.030
0.470 1.816 3.297 0.221 0.031
0.480 1.847 3.410 0.230 0.032
0.490 1.878 3.528 0.240 0.033
0.500 1.911 3.653 0.250 0.034
TABLE 4 delta x = 0.1 0.05 0.01 Correct
when
x y y y y
0.000 1.000 1.000 1.000 1.000
0.100 1.100 1.105 1.110 1.111
0.200 1.220 1.232 1.244 1.247
0.300 1.365 1.388 1.411 1.417
0.400 1.542 1.584 1.625 1.637
0.500 1.764 1.836 1.911 1.934
x^2 dy
0.000 0.050
0.003 0.055
0.010 0.061
0.023 0.067
0.040 0.074
0.063 0.082
0.090 0.092
0.123 0.103
0.160 0.117
0.203 0.135
0.250 0.156
Least Squares Approximation: y = ax + b
Normal Eqns: a x 2
i
+ b xi = xi Y i
a xi + bN = Yi
4)Find the least squares line that fits the following data.
x f(x)=y
1 5.04
2 8.12
3 10.64
4 13.18
5 16.2
6 20.04
Then find the value of f(x) at x = 10.5.