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

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.。

第三章 线性方程组迭代解法§ 3.4 超松弛迭代法(SOR)一、SOR法迭代公式设线性方程组AX=b≠ 0（i=1,2,⋅⋅⋅⋅⋅⋅,n ）。

其中A非奇异，且aii如果已经得到第k次迭代量x (k)及第k+1次迭代量x (k+1)的前i-1个分量（x(k+1),x2 (k+1) ,⋅⋅⋅⋅⋅⋅,x i-1 (k+1) )，1在计算x(k+1)时，先用Gauss-Seidel迭代法得到i(1)选择参数ω，取(2)把 式（1）代入式（2）可以综合写成：即得超松弛法或逐次超松弛迭代法（Successive Over-Relaxation Method），简称SOR法。

或可表示成增量的形式：其中，参数ω叫做松弛因子；若ω=1，它就是Gauss-Seidel迭代法。

令A=D-L-U, SOR 法(2)式可写成：(1)1()1)[(1)]()k k XL D U XD L bωωωωω+--=-++-（D -再整理成：于是可导出SOR 法的矩阵形式：(1)()k k XB Xfω+=+其中，迭代矩阵和f 为:11)[(1)]()B L D U f D L bωωωωωω--⎧=-+⎪⎨=-⎪⎩（D -例3.6 用SOR法求解线性方程组解方程组的精确解为x=(3,4,-5)T，为了进行比较，利用同一初值x(0)=(1,1,1)T，分别取ω=1 (即Gauss-Seidel迭代法)和ω=1.25两组算式同时求解方程组。

①取ω=1 ，即Gauss-Seidel迭代：②取ω=1.25 ，即SOR迭代法：迭代结果见表3.3。

表3.3 Gauss-Seidel迭代法与SOR迭代法比较Gauss-Seidel迭代法SOR迭代法(ω=1.25)k x1x2x3x1x2x30 1.0000000 1.0000000 1.0000000 1.0000000 1.0000000 1.00000001 5.2500000 3.1825000-5.0468750 6.3125000 3.9195313-6.65014652 3.1406250 3.8828125-5.0292969 2.6223145 3.9585266-4.60042383 3.0878906 3.9267587-5.0183105 3.1333027 4.0402646-5.09668634 3.0549316 3.9542236-5.0114410 2.9570512 4.0074838-4.97348975 3.0343323 3.9713898-5.0071526 3.0037211 4.0029250-5.00571356 3.0214577 3.9821186-5.0044703 2.9963276 4.0009262-4.99828227 3.0134110 3.9888241-5.0027940 3.0000498 4.0002586-5.0003486迭代法若要精确到七位小数，◆ Gauss-Seidel迭代法需要34次迭代；◆而用SOR迭代法(ω=1.25)，只需要14次迭代。