数值分析英文版课件 (2)

Answers for Exercises —Numerical methods using MatlabChapter 1P10 2. Solution (a) )(x g x = produces an equation 0862=+-x x . Solving it gives the roots 2=x and 4=x .Since 2)2(=g and 4)4(=g , thus, both 2=P and 4=P are fixed points of )(x g . (b) –(d) The iterative rule using )(x g is 22144n n n p p p ---=. The results for part (b)-(d) with starting value 9.10=p and 8.30=p are listed in Table 1.(e) Calculate values of x x g -='4)( at 2=x and 4=x .12)2(>='g , and 10)4(<='g .Since )(x g ' is continuous, there exists a number 0>δ such that1)(<'x g for all ]4,4[δ+δ-∈x .There also exists a number 0>λ such that1)(>'x g for all ]2,2[λ+λ-∈x .Therefore, 4=p is an attractive fixed point. The sequence generated by22144n n n p p p ---=with starting value 8.30=p converges to 4=p . 2=p is a repelling fixed point. The sequence generated by 22144n n n p p p ---=with starting value 9.10=p does not converge to 2=p .P11 4. Find the fixed point for )(x g : )(x g x = gives 2±=p . Find the derivative: 12)(+='x x g .Evaluate )2(-'g and )2(g ': 3)2(-=-'g , 5)2(='g .Both 2-=p and 2=p gives 1)(>'p g . There is no reason to find the solution(s)using the fixed-point iteration.P11 6. Proof ))(()()(010112p p g p g p g p p -ξ'=-=-)()()( 0101p p K p p g -<-ξ'≤P214. False position method: Assume that ],[n n b a contains the root. The equation of the secand line through ))(,(n n a f a and ))(,(n n b f b is )()()()(n nn n n n b x a b a f b f b f y ---=-. Itintersects x -axise at)()())((n n n n n n n a f b f a b b f b c ---= (Eq. 1.36, p18)1981.0)6.1()(,4907.0)4.2()(00-=-==-=f b f f a f ,8301.1)()())((0000000-=---=a f b f a b b f b c ;Since 0095.0)(0-=c f , then ]8301.1,4.2[],[11--=b a . Similarly, we have1.84093- 1=c , ]1.84093- ,4.2[],[22-=b a 1.84139- 2=c , ]1.84139- ,4.2[],[33-=b a -1.841403=c10. Bisection method: Assume that ],[n n b a contains the root. Then 2nn n b a c +=. (a) 1587.1)4(,4;1425.0)3(,300==-==f b f a , then 5.30=c .Since 03746.0)5.3()(0>==f c f , then ]5.3,3[],[11=b a .Similarly, we can obtain ,,,321c c c . The results are listed in Table 3.The values of tan(x) at midpoints are going to zero while the sequence converges(b) Since 0)3tan(<=, there exist a root in )3,1(..0-=, 055741425.1tan(>)1The results using Bisection method are listed in Table 4.Although the sequence converges, the values of tan (x) at midpoints are not going to zero.P36 2. 3)(2--=x x x f has two zeros 2131±=x . (3028.2,3028.121≈-≈x x ) The first derivative of 3)(2--=x x x f is 12)(-='x x f .The Newton-Raphson iterative function is 123)()()(2-+='-=x x x f x f x x g . The Newton-Raphson formula is 12321-+=+n nn p p p , ,2,1,0=n . The results are listed in Table 5 with starting value p 0=1.6 and p 0=0.0 respectively.Obviously, the sequence generated by the starting value p 0=0.0 does not converge.11. Use Newton-raphson method to solve 0)(3=-=A x x f .The derivative of )(x f is 23)(x x f ='.3232)()()(223x Ax x A x x f x f x x g +=+='-=.Newton-Raphoson formula is 32211--+=n n n p Ap p , ,2,1=n .Since 3A p = is a zero of A x x f -=3)( and 10332)(33<=⎥⎦⎤⎢⎣⎡-='=Ap x A p g ,The sequence generated by the recursive formula 32211--+=n n n p Ap p will converge to3A p = for any starting value ],[330δδ+-∈A A p , where 0>δ.·Answers for Exercises —Numerical methods using MatlabChapter 2P44 2. Solution The 4th equation yields 24=x .Substituting 24=x to the 3rd equation gives 53=x .Substituting both 24=x and 53=x to the 2nd equation produces 32-=x . 21=x is obtained by sustituting all 32-=x , 53=x and 24=x to the 1st equation. The value of the determinant of the coefficient matrix is 115573115=⨯⨯⨯=D .4. Proof (a) Calculating the product of the two given upper-triangular matrices gives⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡++++=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=33333323232222223313231213112212121111113323221312113323221312110000b a b a b a b a b a b a b a b a b a b a b b b b b b a a a a a a B A . It is also an upper-triangular matrix.(b) Let N N ij a A ⨯=)( and N N ij b B ⨯=)( where 0=ij a and 0=ij b when j i >.Let N N ij c B A C ⨯==)(. According to the definition of product of the two matrices, we have ∑==Nk kjik ij b ac 1for all N j i ,,2,1, =.0=ij c when j i > because 0=ij a and 0=ij b when j i >.That means that the product of the two upper-triangular matrices is also upper triangular.5. Solution From the first equation we have 31=x .Substituting 31=x to the second equation gives 22=x .13=x is obtained from the third equation and 14-=x is attained from the last equation.The value of the determinant of the coefficient is 243)1(42)det(-=⨯-⨯⨯=A7. Proof The formula of the back substitution for an N N ⨯upper-triangular system is N NN a b x =and kkNk j jkj k k a x a b x ∑+=-=1 for 1,,2,1 --=N N k .The process requiresN N=+++111 divisions, 22)1()1(212NN N N N -=-=-+++ multiplications, and2)1(212NN N -=-+++ additions or subtractions.P53 1. Solution Using elementary transformations for the augmented matrix gives330012630464275101263046425232103514642],[3231213121⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--−−→−⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---−−−→−⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--=++-+-r r r r r r B AThat means that ⎪⎩⎪⎨⎧=++=++-=-+523 1035 4642321321321x x x x x x x x x is equivalent to⎪⎩⎪⎨⎧==+-=-+33 1263 4642332321x x x x x x The set of solutions is .3,2,1123-===x x x11. Solution Using the algorithm of Gaussian Elimination gives12420010324050110700211242001032409013270021],[212⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡----−−−→−⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--=+-r r B A ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡------−−→−+1242001032005011070021324r r ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡------−−→−+21000103200501107002143r r The set of solutions of the system is obtained by the back substitutions,3,2,2234==-=x x x and .11=x(Chasing method for solving tridiagonal linear systems)14. (a) (i) Solution Applying Gaussian elimination with partial pivoting to the augment matrix results in⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---−−→−⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---=↔1100320001.0101001.01003001.010030001.010*******],[31r r B A ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--−−→−⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--−−→−↔+-+-00043.03333.43019933.996667.630001.0100319933.996667.63000043.03333.430001.01003 3231213231r r r r r r ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---−−−−→−+-6806.00625.680019933.996667.630001.01003326667.633333.43r rThe set of solutions is,101.0524,0100.0-623⨯==x x and .105.2400 -61⨯=x15. Solution The N N ⨯Hilbert matrix is defined byN N ij H H ⨯=)( where 11-+=j i H ij for N j i ≤≤,1.(a) The inverse of the 44⨯ Hilbert matrix is⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--------=-280042001680140420064802700240168027001200120140240120161H The exact solution is T X )140,240,120,16(--=.(b) The solution is T X )0881.185,0628.310,6053.149,7308.18(--=.>>1 H is ill-conditioned. A miss is as good as a mile. (失之毫厘，谬以千里)P62 5 (a) Solving B LY = gives TY )2,12,6,8(-=. From Y UX = we have TX )2,1,1,3(-=. The product of A and X is TAX )4,10,4,8(--=.That means B AX =(b) Similarly to the part (a), we haveTY )1,12,6,28(=, TX )1,2,1,3(=, and B AX T==)4,23,13,28(.6. ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡---=175.113011*********L , ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡-----=5.70001040085304011UP72 7. (a) Jacobi Iterative formula is ()⎪⎪⎩⎪⎪⎨⎧-+=+-=++-=+++)()()1()()()1()()()1(226141358k k k k k k k k k y x z z x y z y x for ,2,1,0=kResults for ),,()()()(k k k k z y x P =’, ,3,2,1=k are listed in Table 2.1 with starting value )0,0,0(0=P .The numerical results show that Jacobi iteration does not converge.(b) Gauss-Seidel Iterative formula is()⎪⎪⎩⎪⎪⎨⎧-+=+-=++-=++++++)1()1()1()()1()1()()()1(226141358k k k k k k k k k y x z z x y z y x for ,2,1,0=kResults ),,()()()(k k k k z y x P =’, ,3,2,1=k are listed in Table 2.2 with starting value )0,0,0(0=P ’Reasons:Conside the eigenvalues of iterative matricesSplit the coefficient matrix ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡----=612114151A into three matrices⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-=--=000100150012004000600010001U L D A .The iterative matrix of Jacobi iteration is⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡----⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=+=-061311041500121041506100010001)(1U L D T JThe spectral raduis of J T is 16800.5)(>=ρJ T . )1176.0,4546405880(i . .-±=λ’ So Jacobi method doesnot converge.Similarly, the iterative matrix of Gauss-Seidel iteration is⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--=-=-65503200150)(1U L D T G .The spectral radius of G T is 2532.19)(=ρG T >1. )0866.0,2532.19,0(-=λ’ So Gauss-Seidel method does not converge.8. (a) Jacobi Iterative formula is()⎪⎩⎪⎨⎧-+=-+=+-=+++6/225/)8(4/)13()()()1()()()1()()()1(k k k k k k k k k y x z z x y z y x for ,2,1,0=k ),,()()()(k k k k z y x P =’ for 10,,2,1 =k are listed in Table 2.3 with starting value )0,0,0(0=P .Jacobi iteration converges to the solution (3, 2, 1)’(b) Gauss-Seidel iterative formula is()⎪⎪⎩⎪⎪⎨⎧+---=+---=+-=++++++)1()1()1()()1()1()()()1(22614/)8(4/)13(k k k k k k k k k y x z z x y z y x for ,2,1,0=k ),,()()()(k k k k z y x P =’ for 10,,2,1 =k are listed in Table 2.4 with starting value )0,0,0(0=PGauss-Seidel iteration converges to the solution (3, 2, 1)’Answers for Exercises —Numerical methods using MatlabChapter 3P99 1. Solution (a) The nth order derivative of )sin()(x x f = is )2sin()()(π+=n x x f n .Therefore, !5!3)(535x x x x P +-=, !7!5!3)(7537x x x x x P -+-= and !9!7!5!3)(97539x x x x x x P +-+-=.(b) Estimating the remainder term gives71091075574.2!101!10)5sin()(-⨯≤≤π+=x c x E for 1≤x .(c) Substituting 4π=x to )2sin()()(π+=n x x f n gives ,22)4()4(,22)4()4()3(-=π=π''=π'=πf f f f and 22)4()4()5()4(-=π=πf f .By using Taylor polynomial we have!5)4(22!4)4(22!3)4(22!2)4(22)4(2222)(54325π-+π-+π--π--π-+=x x x x x x P P108 1. (a) Using th e Horner ’s method to find )4(P givesSo )4(P =1.18.(b) From part (a) we have 12.002.002.0)(2-+-=x x x Q . )4()4(Q P =' can be also obtained byusing Horner ’s method.So )4(P '=-0.36 Another method:Hence, P(4)=-0.36.(c) Find )4(I and )1(I firstly.Then=-=⎰)1()4()(41I I dx x P 4.3029.(d) Use Horner ’s method to evaluate P (5.5)Hence, P (5.5)=0.2575.(d) Let 012233)(a x a x a x a x P +++=. There are 4 coefficients needed to found.Substituting four known point ),(i i y x , i =1, 2, 3, 4, into )(x P gives four linear equations with unknowni a , i =1, 2, 3, 4.54.10123=+++a a a a 5.12480123=+++a a a a 42.139270123=+++a a a a 66.05251250123=+++a a a aThe coefficients can be found by solving this linear system: .66.1,2.0,1.0,02.00123=-==-=a a a aP120 1. The values of f (x ) at the given points are listed in Table 3.1:(a) Find the Lagrange coefficient polynomials and 010)(0,1x x x L -=---=.1101)(1,1+=++=x x x LThe interpolating polynomial is x x L f x L f x P =+-=)()0()()1()(1,10,11. (b) ),(21)11()1()(20,2x x x x x L -=----=,110)1)(1()(21,2x x x x L -=--+=),(212)1()(22,2x x x x x L +=+=x x L f x L f x L f x P =++-=)()1()()0()()1()(2,21,20,22. (c) ),2)(1(61)21)(11()2)(1()(0,3---=-------=x x x x x x x L),2)(1)(1(21)20)(10)(10()2)(1)(1()(1,3--+=--+--+=x x x x x x x L),2)(1(21)21(1)11()2()1()(2,3-+-=-+-+=x x x x x x x L),1)(1(61)12(2)12()1()1()(3,3-+=-+-+=x x x x x x x L33,32,31,30,33)()2()()1()()0()()1()(x x L f x L f x L f x L f x P =+++-=(d) ,2212)(0,1x x x L -=--=,1121)(0,1-=--=x x x L 67)()2()()1()(1,10,11-=+=x x L f x L f x P . (e) ),23(21)20)(10()2)(1()(20,2+-=----=x x x x x L ),2()21(1)2()(21,2x x x x x L --=--=),(21)12(2)1()(20,2x x x x x L -=--=.23)()2()()1()()0()(22,21,20,22x x x L f x L f x L f x P -=++=7. (a) Note that each Lagrange polynomial )(,2x L k is of degree at most 2 and )(x g is a combination of)(,2x L k . Hence )(x g is also a polynomial of degree at most 2.(b) For each k x , 2,1,0=k , the Lagrange coefficient polynomial 1)(,2=k k x L , and 0)(,2=k j x L for k j ≠, 2,1,0=j . Therefore, 01)()()()(2,21,20,2=-++=k k k k x L x L x L x g .(c) )(x g is a polynomial of degree 2≤n and has n ≥ 3 zeroes. According to the fundamental theorem of algebra, 0)(=x g for all x .9. Let )()()(x P x f x E N N -=. )(x E N is a polynomial of degree N ≤.)(x f is degree with )(x P N at N +1 points N x x x ,,,10 implies that )(x E N has N +1 zeroes. Therefore, 0)(=x E N for all x , that is, )()(x P x f N = for all x .P131 6. (a) Find the divided-difference table:(b) Find the Newton polynomials with order 1, 2, 3 and 4.)0.1(80.16.3)(1--=x x P , )0.2)(0.1(6.0)0.1(80.160.3)(2--+--=x x x x P ,)0.3)(0.2)(0.1(15.0)0.2)(0.1(6.0)0.1(80.16.3)(3------+--=x x x x x x x P , )0.4)(0.3)(0.2)(0.1(03.0 )0.3)(0.2)(0.1(15.0)0.2)(0.1(6.0)0.1(80.16.3)(4----+------+--=x x x x x x x x x x x P .(c)–(d) The results are listed in Table 3.2P143 6. x x x T 32)(323-=, ]1,1[-∈x .The derivative of )(3x T is 323)(223-⋅='x x T . 0)(3='x T yields 21±=x . Evaluating )(3x T at 21±=x and 1±=x gives 1)1(3-=-T , 1)21(3=-T , 1)21(3-=T and 1)1(3=T .Therefore, 1))(max(3=x T , 1))(min(3-=x T .10. When 2=N , the Chebyshev nodes are ,23)6/5cos(0-=π=x ,01=x and 23)6/cos(2=π=x .Calculating the Lagrange coefficient polynomials based on 210,,x x x can produce the following results:,323)232(23)23()(20,2x x x x x L +-=⨯-⨯--=,341)23(23)23()23()(21,2x x x x L -=-⨯-+=.32323232)23()(22,2x x x x x L +=⨯⨯+=The proof is finished.Answers for Exercises —Numerical methods using MatlabChapter 4P157 1(a). Solution The sums for obtaining Normal equations are listed in Table 4.1The normal equations are ,710=A 135=B . Then ,7.0=A 6.2=B .The least-squares line is 6.27.0+=x y .2449.0)((51)(215122=⎪⎪⎭⎫ ⎝⎛-=∑=k k k x f y f EP158 4. Proof Suppose the linear-squares line is B Ax y += where A and B satisfiesthe Normal equations ∑∑===+N k k Nk ky xAB N 11and ∑∑∑====+Nk k k N k k N k k y x x A x B 1121.y y N x A B N N B x N A B x A N k k Nk k N k k ==⎪⎪⎭⎫ ⎝⎛+=+⎪⎪⎭⎫ ⎝⎛=+∑∑∑===111111 meas thatthe point ),(y x lies on the linear-squares line B Ax y +=.5. First eliminating B on the Normal equations∑∑===+Nk k Nk k y x A B N 11and ∑∑∑====+Nk k k Nk k Nk k y x x A x B 1121gives⎪⎪⎭⎫ ⎝⎛-=∑∑∑===Nk k N k k N k k k y x y x N D A 1111 where 2112⎪⎪⎭⎫ ⎝⎛-=∑∑==N k k N k k x x N D . Substituting A into the first equation gets⎪⎪⎭⎫⎝⎛⎪⎪⎭⎫ ⎝⎛+-=∑∑∑∑∑=====Nk k Nk k N k k k N k k N k k y x N y x x y N D D B 12111111. Note that ∑∑∑∑∑∑∑∑========⎪⎪⎭⎫ ⎝⎛-=⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛-=N k k N k k N k k N k k N k k N k k N k k Nk k y x N y x y x x N N y N D 12111212112111. Simplifying B gives⎪⎪⎭⎫ ⎝⎛-=∑∑∑∑====Nk k k N k k Nk k N k k y x x y x D B 111121.8(b). The sums needed in the Normal equations are listed in Table 4.26177.142==∑∑k kk x y x A )2(=M5606.063==∑∑kkkxy x B )3(=MHence, 26177.1x y = and 35606.0x y =.0.3594 )(51)(21512222=⎪⎪⎭⎫ ⎝⎛-=∑=k k k Ax y Ax E , 1.1649 )(51)(21512332=⎪⎪⎭⎫ ⎝⎛-=∑=k k k Bx y Bx E .26175.1x y =fits the given data better.P171 2(c). The sums for normal equations are listed in Table 4.3.Using the formula∑∑∑∑∑∑∑========++=++52545352515135125151512515k kk k k k k k k k kk k k ky x x A x B x C y x A xB Cproduces the system with unkowns A , B , and CSolving the obove system gives .6.0,1.0,5.2-=-==C B A The fitting curve is .6.01.05.22--=x x yP172 4. (a) Translate points in x-y plane into X-Y plane using y Y x X ln ,==. The results arelisted in Table 4.4.The Normal equationsgive the system .793410,110,22105=+-==+A C B A C ∑∑∑∑∑======+=+515125151515k kk k k k k k kk k Y X X A X B Y X A B .8648.0155,2196.455-=+=+A B A BThen -0.50844=A , 1.3524=B . Thus 866731.3524.e e C B ===.The fitting curve is xe .y 50844.086673-=, and 1190.0)((51)(215122=⎪⎪⎭⎫ ⎝⎛-=∑=k k k x f y f E .(b) Translate points in x-y plane into X-Y plane using yY x X 1,==. The results are listed in Table 4.5.The Normal equationsgive the system Then 2432.0=A , 30280.0=B .The fitting curve is 30280.02432.01+=x y and 5548.4)((51)(215122=⎪⎪⎭⎫ ⎝⎛-=∑=k k k x f y f E .(c) It is easy to see that the exponential function is better comparing with errors in part (a) and part (b)..1620.5155,7300.255=+=+A B A B ∑∑∑∑∑======+=+515125151515k kk k k k k k kk k Y X X A X B Y X A BP188 1. (a) Derivativing )(x S gives 232132)(x a x a a x S ++='. Substituting the conditions intothe derivative pruduces the system of equations . 012428420321 32132103213210⎪⎪⎩⎪⎪⎨⎧=++=+++=++=+++a a a a a a a a a a a a a a (b) Solving the linear system of equations in (a) gives 29,,12,63210-==-==a a a a . The cubic polynomial is 3229126)(x x x x S -+-=.Figure: Graph of the cubic polynomial4. Step 1 Find the quantities: 3,1210===h h h , 21/)20(/)(0010-=-=-=h y y d13/)03(/)(1121=-=-=h y y d , 6667.03/)31(/)(2232-=-=-=h y y d18)(6011=-=d d u , 10)(6122-=-=d d uStep 2 Use ⎪⎪⎩⎪⎪⎨⎧-'-=⎪⎭⎫ ⎝⎛++'--=+⎪⎭⎫⎝⎛+))((3232))((32232322211100121110d x S u m h h m h x S d u m h m h h to obtain the linear system⎩⎨⎧-=+=+0001.155.1032135.72121m m m m .The solutions are 5161.2,8065.321-==m m . Step 3 Compute 0m and 3m using clamaped boundary.4.90322))((310000-=-'-=m x S d h m , 2.92482))((322323=--'=md x S h m Step 4 Find the spline coefficients16)2(,210001,000,0-=+-===m m h d s y s , 1.45166,-2.45162013,002,0=-===h m m s m s ;-1.54856)2(,021111,110,1=+-===m m h d s y s , -0.35136,1.903321123,112,1=-===h m m s m s ;0.38716)2(,332221,220,2=+-===m m h d s y s , 0.30236,-1.258122233,222,2=-===h m m s m s ;Step 5 The cubic spline is320)3(4516.1)3(4516.2)3(2)()(+++-+-==x x x x S x S for 23-≤≤-x ,321)2(3513.0)2(903.1)2(5484.1)()(+-+++-==x x x x S x S for 12≤≤-x , and322)1(3023.0)1(2581.1)1(3871.03)()(-+---+==x x x x S x S for 41≤≤x .5. Calculate the quantities: 3,1210===h h h , 20-=d ,11=d , 6667.02-=d ,181=u , 102-=u . ( Same values as Ex. 4)Substituting }{j h , }{j d and }{j u into ()()⎩⎨⎧=++=++22211112111022u m h h m h u m h m h h gives ⎩⎨⎧-=+=+1012318382121m m m mSolve the linear equation to obtain .5402.1,8276.221-==m m In addition, .030==m m Use formula (4. 65) to find the spline coefficients:4713.26)2(,210001,000,0-=+-===m m h d s y s , 4713.06,020013,002,0=-===h m m s m s ;-1.05756)2(,021111,110,1=+-===m m h d s y s , -0.24276,4138.121123,112,1=-===h m m s m s ;8735.06)2(,332221,220,2=+-===m m h d s y s , 0856.06,7701.0-22233,222,2=-===h m m s m s .Therefore, 30)3(4713.0)3(4713.22)(+++-=x x x S , for 23-≤≤-x ;321)2(2427.0)2(4138.1)2(0575.1)(+-+++-=x x x x S , for 12≤≤-x322)1(0856.0)1(7701.0)1(8735.03)(-+---+=x x x x S for 41≤≤x .Answers for Exercises —Numerical methods using MatlabChapter 5P209 1(b). Solution LetThe result of using the trapezoidal rule with h =1 isUsing Simpson’s rule with h=1/2, we haveFor Simpson’s 3/8 rule with h=1/3, we obtainThe result of using the Boole’s rule with h=1/4 is4. Proof Integrate )(1x P over ],[10x x .110102012101)(2)(2)(xx x x x x x x h f x x h f dx x P -+--=⎰=)(210f f h +. The Quadrature formula )(2)(1010f f hdx x f x x +≈⎰is called the trapezoidal rule.6. Solution The Simpson ’s rule is)4(3)(21010f f f hdx x f x x ++≈⎰. It will suffice to apply Simpson ’s rule over the interval [0, 2] with the test functions32,,,1)(x x x x f = and 4,x . For the first four functions, since)1141(31212+⨯+==⎰dx , )2140(31220+⨯+==⎰xdx , )4140(3138202+⨯+==⎰dx x , )8140(314203+⨯+==⎰dx x , the Simpson ’s rule is exact. But for 4)(x x f =,)16140(3153224+⨯+≠=⎰dx x . .Therefore, the degree of precision of Simpson ’s rule is n =3.T he Simpson’s rule and the Simpson ’s 3/8 rule have the same degree of precision n =3.).4cos(1)(x e x f x -+=..f f f f h dx x f 3797691))1()0((21)(2)(1010=+=+≈⎰.9583190))1()5.0(4)0((61)4(3)(21010. f f f f f f h dx x f =++=++≈⎰.9869270 ))1()3/2(3)3/1(3)0(( 8/1 )33(83)(321010.f f f f f f f f hdx x f =+++=+++≈⎰.008761 ))1(7)4/3(32)2/1(12)4/1(32)0(7( 90/1 )73212327(452)(432101.f f f f f f f f f f hdx x f =++++=++++≈⎰P220 3(a) Solution When 3)(x x f =for 10≤≤x , ⎰+π=123912dx x x area .The values of 2391)(x x x g +=at 11 sample points (M =10) are listed in the Table 5.1:(i) Using the composite Trapezoidal rule ∑-=++=110)()()((2),(M k k M x g h x g x g hh g T , the computation is)9156.11084.16098.03719.01563.00710.00280.00081.00010.0(101)1623.30(201)101,(++++++++++=g T=)2160.4(101)1623.3(201+=0.1576+0.4216=0.5792.(ii) Using the composite Simposon ’s rule ∑∑-=--=+++=11121120)(34)(32)()((3),(M k k M k k M x g h x g h x g x g h h g S , the computation is)9156.16098.01563.00280.00010.0(304)1084.13719.00710.00081.0(302 )1623.30(301)101,(++++++++++=g S=)7106.2(304)5054.1(302 )1623.3(301++=0.5672.7. (a) Because the formula)2()1()0()(2102g w g w g w dt t g ++=⎰is exact for the three functions 1)(=t g ,x t g =)(, and 2)(x t g =, we obtain three equations with unkowns 0w , 1w , and 2w :2210=++w w w , 2221=+w w ,38421=+w w . Solving this linear system gives 310=w , 341=w and 312=w .Thus, ())2()1(4)0(31)(20g g g dt t g ++=⎰(b) Let ht x x +=0 and denote ,01h x x +=.202h x x +=Then the change of variable ht x x +=0 translates ],[20x x into [0, 2] and converts the integral expresion dx x f )( into dt ht x hf )(0+. Hence,()())()(4)(3)2()1(4)0(3)()()(21022002x f x f x f h g g g hdt t g h dt ht x f h dx x f x x ++=++==+=⎰⎰⎰. The formula ())()(4)(3)(21020x f x f x f hdx x f x x ++=⎰ is known as the Simpson ’s rule over ],[20x x .8(a).9(a).P234 1(a) Let 212sin )(x xx f +=. The Romberg table with three rows for ⎰+3212sin dx x xis given as follows:Where04191.0)02794.0(23)106sin 0(23))3()0((23)0()0,0(-=-=+=+==f f T R , 04418.0)5.113sin (5.1204191.0)5.1(5.12)0()1()0,1(2=++-=+==f T T R ,3800.0)25.215.4sin 75.015.1sin (75.0204418.0))25.2()75.0((75.02)1()2()0,2(22=++++=++==f f T T R , 07288.03)04191.0(04418.043)0,0()0,1(4)1()1,1(=--⨯=-==R R S R ,].6/,6/[],[ and cos )(Let ππ-==b a x x f have we , and cos )( ,sin )( Since Mab h x x f x x f -=-=''-='.10513/123/ )(12),(922-⨯<⨯⎪⎭⎫ ⎝⎛ππ≤''--=M c f h a b h f E T .1039.2/)( and )4375( 9.4374 So,4-⨯≈-==>M a b h M M ].6/,6/[],[ andcos )(Let ππ-==b a x x f ,cos )( ,sin )( , cos )( ,sin )( Since )4(x x f x x f x x f x x f =='''-=''-='.105123/1803/ )(180),(92)4(4-⨯<⨯⎪⎭⎫ ⎝⎛ππ≤--=M c f h a b h f E S havewe ,2 and M a b h -=.1027.92/)( and )565( 8.564 So,4-⨯≈-==>M a b h M M4919.0304418.03800.043)0,1()0,2(4)2()1,2(=-⨯=-==R R S R ,5198.0307288.04919.01615)1,1()1,2(16)2()2,2(=-⨯=-==R R B R ,2. Proof If L J T J =∞→)(lim , thenL LL J T J T J S J J =-=--=∞→∞→343)1()(4lim)(lim andL LL J S J S J B J J =-=--=∞→∞→151615)1()(16lim )(lim .9. (a) Let 78)(x x f =. 0)()8(=x f implies 4=K . Thus 256)4,4(=R .(b) Let 1011)(x x f =.0)()11(=x f implies 5=K . Thus 2048)5,5(=R .10. (a) Do variable translation t x =. Thendt t dt t t dx x tx ⎰⎰⎰=⋅===121122.That means the two integrals dx x ⎰1anddt t ⎰122have the same numerical value.(b) Let 22)(t t f = and x x g =)(.Use dt t R ⎰≈122)1,1( means that the truncation error is )()4(n f k ξ approximately.Note that 0)()3(=t f . It means )1,1(212R dt t =⎰.But for x x g =)(, 0)()(=x g n is not true for all ]1,0[∈x and any integer 0>n .Thus the Romberg sequence is faster for dt t ⎰122 than fordx x ⎰1even though they have the samenumerical value.P242 1 (a) Applying the change of variable 22ab x a b t ++-=to dt t ⎰256 givesdx x dt t x t ⎰⎰-+=+⋅==115125)1(66.Thus the two integrals are dt t ⎰256 anddx x ⎰-+⋅115)1(6equivalent.(b)315315311525)1(6)1(6)()1(66=-=-+++=≈+⋅=⎰⎰x x x x f G dx x dt t =0.0809 +58.5857=58.6667If using )(3f G to approximate the integral, The result is535055353115205)1(695)1(698)1(695)()1(66==-=-+++++=≈+⋅=⎰⎰x x x x x x f G dx x dt t64105.5965956.0000 98 0.0035 95=⨯+⨯+⨯=6. Analysis: The fact that the degree of precision of N -point Gauss-Legendra integration is 2N -1 impliesthat the error term can be represented in the form )()()2(c kf f E N N =.(a) Since dt t dx x tx ⎰⎰-+=+==117127)1(88, and ()0)1()8(7=+t implies 82=K . Thus =256)(4=f G .(b),)1(111111101210dt t dx x tx ⎰⎰-+=+==and ()0)1()11(10=+t implies 122=K .Thusdx x⎰21011=2048)(6=f G .7. The n th Legendre polynomial is defined by The first five polynomials areThe roots of them are same as ones in Table 5.8.11. The conditions that the relation is exact for the functions means the three equations:326.0 6.0 0)6.0( )6.0(2 3132111321=+=+-=++w w w w w w w Sloving the system gives 98 ,95 231===w w w . ))6.0((95)0(98))6.0((95)(212111f f f dx x f ++-≈⎰- is called three-point Gauss-Legendre rule.Answers for Exercises —Numerical methods using MatlabChapter 6P249 1. (a) Proof Differentiate 22)(2+-+=-t t Ce t y t .22)(-+-='-t Ce t y tSubstitute )(t y and )(t y ' into the right-hand side of the equation y t y -='2.side left )(22)22(side right 222='=-+-=+-+-=-=--t y t Ce t t Ce t y t t t(b) Solution Let y t y t f -=2),(. Then 1),(-=y t f y for any ),(y t .So, the Lipschitz constant is 1=L .()[],2,11!21)(1)(20=-⋅==n x dx d n x P x P nnn n n ()()()3303581)(3521)(1321)()(1)(244332210+-=-=-===x x x P x x P x x P x x P x P 2,,1)(x x x f =12 . Integrate both side of )(t f y =' over [a , b ]: ⎰⎰='=-babadt t f dt y a y b y )()()(.Then,)()()(a y b y dt t f ba-=⎰, where )(t y is the solution of the I. V . P)(t f y =', for b t a ≤≤ with 0)(=a y . That means that the definite integral⎰badt t f )( can becomputed using the two values )(a y and )(b y of the solution )(t y of the given I. V . P.. 14. Solution Separate the two variables of the equation 211t y +=' into the form dt tdy 211+=. Integrate dt tdy 211+=and yeild the general solution C t y +=arctan . The initial-value condition 0)0(=y means that 0=C . The solution for the I. V . P. is t y arctan =.P257 3. (a)-(c) The formula using Euler ’s method to solve the I. V . P. ty y -=', 1)0(=y canbe represented in the form k k k y ht y )1(1-=+. When 2.0=h and 1.0=h , the results are listed in Table 6.1.(d) The F. G . E. does decrease half approximatelly as expacted when h is halved.6. When 02.0=a , 00004.0=b and 10=h , the Euler ’s formula for 2bP aP P -=' is in the form210004.02.1k k k P P P -=+. With 1.760=P , the missing entries can be filled in the table.。

第一章绪论截断误差truncation error舍入误差rounding error; round-off error绝对误差absolute error误差限bounds on error相对误差relative error相对误差限bounds on relative error有效数字significant digit; significant figure数值稳定性numerical stability第二章插值与拟合插值函数interpolating function插值节点interpolation knot; interpolation node插值区间插值多项式interpolation polynomial基函数base function差商difference coefficient向前差分forward difference quotient向后差分backward difference quotient中心差分central difference向前差分算子forward difference operator向后差分算子backward difference operator中心差分算子central difference operator不变算子invariant operator移位算子shifting operator三次样条函数cubic spline function三次样条插值函数cubic spline interpolating function 边界条件boundary condition自然边界条件natural boundary condition周期边界条件period boundary condition最小二乘法曲线拟合least squares curve fitting法方程normal equation第三章数值积分与数值微分数值积分numerical integration数值微分numerical differentiation求积公式quadrature formula求积节点quadrature knot求积系数quadrature coefficients代数精度algebraic accuracy插值型求积公式interpolatory quadrature formula余项remainder term外推法extrapolation method第四章解线性方程组的直接方法消去法cancellation method三角分解法triangular decomposition平方根法square root method追赶法forward elimination and backward substitution 范数norm条件数condition number第五章解线性方程组的迭代法迭代法iteration method收敛convergence发散diverge超松弛迭代法successive over relaxation method第六章非线性方程求根二分法dichotomy method不动点fixed point牛顿法Newton method第八章矩阵特征值问题计算特征值characteristic value特征向量character vector幂法power method反幂法inverse power method。

1.1 Introduction to numerical analysisNumerical analysis is the main part of Computional Methods. It involves the study, development, and analysis of algorithms for obtaining numerical solutions to various mathematical problems.For example:Growth of a Population An Exponential Model is as follows:Let denote the number at time t and denote the constant birth rate of thepopulation.Suppose that immigration is permitted at a constant rate , then the population satisfiesthe differentialequationWhose solution iswhere denotes the initial population.Suppose a certain population contains 1,000,000 individuals initially, that 435,000 individuals immigrate into the community in the first year, and that 1,564,000 individuals are present at the end of the one year.To determine the birth rate of this population, we must solve the equationof which the exact solution cannot be obtained by algebraic methods.This problem is equivalent to finding a solution of an equation of the form .We will discuss how to solve this problem in Chapter 2. Textbook (not necessarily to have):Numerical Analysis (Seventh Edition) 数值分析 （第七版 影印版）Richard L. Burden & J. Douglas Faires （高等教育出版社） 1.2 Roundoff Errors and Computer ArithmeticThe arithmetic performed by a calculator or computer is different from the arithmetic in our algebra and calculus courses.In our traditional math world, we permit numbers with an infinite number of digits. For exampleComputers use floating point numbers which have 3 parts: ● Sign● Characteristic● MantissaFor the 64-bit (binary digit) representation, a machine number looks like0 10000000011 10111001000100000 (00000000000)The first bit is a sign indicator, denoted s.Followed by an 11-bit component, c , called the characteristic.And a 52-bit binary fraction, f , called the mantissa. υλ+=)(d )(d t N t t N )(t N λv )1()(0-+=t t e e N t N λλλν0N )1(000,435000,000,1000,564,1-+=λλλe e 0)(=x f ()3332844222==⋅=+)76.4,93.1(),(),24.3,31.1(),(1100==y x y xUsing this system,we give a floating-point number of the formThe smallest positive number that can be represented hasNumbers occurring in calculations that have a magnitude less than this value results in underflow and are generally set to zero.The largest positive number that can be represented hasNumbers occurring in calculations that have a magnitude greater than this value results overflow and typically cause the computation to stop.Round-off ErrorsThe error is produced when a calculator or computer is used to perform real-number calculations. k-digit decimal machine numbers: machine numbers that are in the following normalized decimal floating point formAny positive real number within the numerical range of the machine can be normalized to theformThe floating-point form of y, denoted fl(y ), is obtained by terminating the mantissa of y at kdecimal digits ,There are two ways of performing this termination.• Chopping• RoundingIf is an approximation to , then• The absolute error is• The relative error is provided thatFor exampleConclusions:• The example shows that the same relative error)1(2)1(1023f c s +--4096156212311618121 2112112112112112111027121024 212120202101285431012910+++++=⎪⎭⎫ ⎝⎛⋅+⎪⎭⎫ ⎝⎛⋅+⎪⎭⎫ ⎝⎛⋅+⎪⎭⎫ ⎝⎛⋅+⎪⎭⎫ ⎝⎛⋅+⎪⎭⎫ ⎝⎛⋅==++=⋅+⋅+⋅++⋅+⋅==f c s 0,1,0===f c s 307102310102225.0)01(2)1(--⨯≈+-5221,2047,0--===f c s 309521023204701017977.0)211(2)1(⨯≈-+---.,,3,290 91,10.0121k i d d d d d i n k =≤≤≤≤⨯±，，.10.02121n k k k d d d d d y ⨯=++ .10.0)(fl 21n k d d d y ⨯=1030.333 is error relative and 10 0.1 is error absolute 103100.0,103000.0)c 1030.333 is error relative and 10 0.1 is error absolute 103100.0,103000.0)b 1030.333 is error relative and 0.1 is errorabsolute 103100.0,103000.0)a 1-34*41-4-3*31-1*1⨯⨯⨯=⨯=⨯⨯⨯=⨯=⨯⨯=⨯=--p p p p p p ,103333.01-⨯*p p .*p p -,/*p p p -.0≠poccurs for widely varying absolute errors. • As a measure of accuracy, the absolute error can be misleading and the relative error more meaningful since the relative error takes into consideration the size of the value. Significant Digits (有效数字) Definition: The number is said to approximate p to t significant digits if t is the largest nonnegative integer for whichExamples 1Real value: 10/3Approximate value: 3.3333Absolute error: 1/30000Relative error: 1/100000Number of significant digits = 5Examples 2Approximate values x 1=1.73, x 2=1.7321, x 3=1.7320, determine the digits of significance.Computer ArithmaticIn addition to inaccurate representation of numbers, the arithmetic performed in a computer is not exact.For exampleCalculations which produce the erros are given as follows:1. One of the most common error-producing calculations involves the cancellation of significantdigits due to the substracton of nearly equal numbers.So, we should avoid subtraction of nearly equal numbers!!2. If a finite-digit representation or calculation introduces an error, further enlargement of theerror occurs when divided by a number with small magtitude (or, equivalently, when multiplying by a number with large magnitude).So, we should avoid division by a small number!))()(( ))()(())()(( ))()((y fl x fl fl y x y fl x fl fl y x y fl x fl fl y x y fl x fl fl y x ÷=÷⨯=⊗-=+=⊕52210500005.03-⨯=≈-=x e 433105000051.03-⨯<≈-=x e 3 digits3111050021.03-⨯<≈-=x e 4 digits5 digits t *p tp p p -⨯≤-105 :error relative the *...7320508.13==x 8163972286.0101732.0101414.03211=⨯⨯=How to reduce the roundoff error?1. The loss of accuracy due to roundoff error can ofen be avoided by a reformulation of the problem.2. Accuracy loss dute to roundoff error can also be reduced by rearranging calculations. Oneway to reduce roundoff error is to reduce the number of error-producing computations.Homeworks.⏹ Page 27 Q. 4Perform the following computations(i)exactly,(ii)using three-digit chopping arithmetic,(iii)using thrree-digit rounding arithmetic.(iv)Compute the relative errors in parts(ii)and (iii).⏹ Page 28 Q. 15Use the 64-bit long real format to find the decimalequivalent of the following floating-pint machine number.a. 0 10000001010 10010011000000 (000)⏹ Page 28 Q. 17Suppose two points andare on a straight line with Two formulas are available to find the x-intercept of the line:a. Show that both formulas are algebraically correct.b. Use the data and three-digit rounding arithmetic to compute the x-intercept both ways. Which method is better and why1.3 Algorithm and convergenceAn algorithm is a procedure that describes, in an umambiguous manner, a finite sequence of steps to be performed in a specified order.The object of algorithm is to implement a procedure to solve a problem or approximate a solution to the problem.We use a pseudocode to describe the algorithm.This pseudocode specifies the form of the inpute to be supplied and the form of the desired output. Not all numerical procedures give satisfactory output for arbitrary chosen input.As a consequence, a stopping technique independent of numerical technique is incorporated into each algorithm to avoid infinite loops.The steps in the algorithms follow the rules of structured program consruction. They have been arranged so that there should be minimal difficulty translating pseudocode into any programming language suitable for scientific applications.Since iterative techniques involving sequences are often used, now we concludes with a brief 20311331c.+⎪⎭⎫ ⎝⎛-)76.4,93.1(),(),24.3,31.1(),(1100==y x y x 010010010110)(y y y x x x x and y y y x y x x ---=--=),(00y x ),(11y x 01y y ≠discussion of some terminology used to describe the rate at which convergence occurs when employing a numerical techniques. In general, we would like the technique to converge as rapidly as possible.Although this definiton permites {}∞=1n n α to be compared with an arbitrary seqence {}∞=1n n β, in nearly every situation we use p n n 1=βfor some numberp>0. We are generally interested in the largest value of p with )(n n O βαα+=.The following definitons describes the rate at which functions converge.The functions we use for comparision generally have the form p h h G =)(,where p>0. We are interested in the largest value of p with )(F(h)p h O L +=.{}{}{}).().(,arg ,tan ,111n n n n n n n n n n n O writing by indicated is This O e convergenc of rate with to converges that say we then n e l for K with exitst K t cons positive a If to converges and zero to known sequence a is Suppse Definition βααβααβααααβ+=≤-∞=∞=∞=)).((F(h) write ,,)()(tan )(lim 0)(lim 0h 0h h G O L we then h small tly suffficien for h G K L h F with exitst K t cons positive a If L h F and h G that Suppse Definition +=≤-==→→。