《数学数值分析》PPT课件.ppt_第1页
《数学数值分析》PPT课件.ppt_第2页
《数学数值分析》PPT课件.ppt_第3页
《数学数值分析》PPT课件.ppt_第4页
《数学数值分析》PPT课件.ppt_第5页
已阅读5页,还剩41页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第九章 线性与非线性方程组的迭代解法 /* iteration methods for the solution of linear or nonlinear systems */ Linear systems: A x = b Matrix form Ax=b A x* =b x(k+1)=f(x(k) ) x(k), k=0,1,2, hopefully, limx(k)=x* Iterative method: given a linear system Ax=b, design an iteration formula x(k+1)=f(x(k) and choose an initial approximate solution x(0). iteration results in a series approximate solutions x(k)|kZ which approaches to the real solution x* hopefully. x(0 ) How to design the iteration formula? LUD Ax=bx=Bx+f x(k+1)=B x(k) +f Jacobi iteration Matrix form Component form Convenient in programming Gauss- Seidel iteration Component form Convenient in programming Matrix form comparison Jacobi iterationGauss-Seidel iteration 计算x(k+1)时需要x(k)的 所有分量,因此需开 两组存储单元分别存 放x(k)和x(k+1) 计算xi(k+1)时只需要 x(k)的i+1n个分量, 因此x(k+1)的前i个分量 可存贮在x(k)的前i个 分量所占的存储单元 ,无需开两组存储单 元 Convergence of iteration Convergence of matrix Error vector of iteration exampleJacobi iteration G-S iteration How to check if a certain iteration system converges or not? Conditions of convergence Not flexible to use actually Posterior error estimated in the process of iteration Prior error estimated before the iteration Proof: from Jordan standard form of B, we know column j+1 Row j+1 Proof: From above, we have Summary: 1. Bp或(B)越小,迭代法的收敛速度越快; 2. 若事先给出误差精度,由事先误差估计式可得到迭代 次数的估计 3. 实际计算中,若Bp不太接近于1,利用事后误差 估计作为控制迭代停止的条件,即当 x(k)-x(k-1)p1,over relaxed W=1,G-S Suppose has been found by using G-S, now we have to find SORsuccessive over relaxed methodacceleration of G-S iteration Residual of two successive iteration results Matrix form Coordinate /component form Vector form Both sides times D Convergency of SOR Conditions of convergence Proof: :necessary condition. In order to SOR converge,we must choose 00, i=1,2,n 0 00 Example 5 Solve the following linear system using J,G-S,and SOR(w=1.15). Iteration halts when Solution: take 1.Jacobi iteration 2.Gauss-Seidel iteration 3.SOR !note: w chosed well, SOR converges very fast. As for J and G-S, the convergence speed depends on the spectral radius of the iteration matrix. !NOTE: 1. The key problem in SOR is how to choose such a w that SOR converges fastest-the problem of how to choose the best relaxed factor w. Presently, the problem has been solved for a few special matrices. For the general case, successive searching method is used. At the start, choose one or more different w to try SOR. Then modify w according to the speed of convergence and successively find the best w. Finally fix w and continue iteration. 2. In theory, by iteration we can get approximate solution to any accuracy expected. Actually, however, due to the limit of computer word length, we cant arrive at any accuracy but the machine accuracy at most. So when we use to control iteration halting, we must be careful in choosing in that machine accuracy or less results in dead loop. iteration methods for the solution of nonlinear systems Nonlinear system: f1, f2, fn-nonlinear functions Basic idea of iteration for the solution of 1-dim nonlinear function f(x)=0: Condition for convergence: Real root Initial point Iteration for nonlinear system: Condition for convergence: Sufficient(not necessary) condition for the iteration converging Example 6 Solution : Converges! Newtons method(Newton-Raphson method)root finding for nonlinear function y=f(x) Basic idea for 1-d nonlinear functions (x0,f(x0 ) (x1,f(x1 ) y=f(x) root x* f(x*)=0 x y In the vicinity of x* Check if f(x0 ) , find another approximate root x1 using bisection, newtons method,etc. Secant methodroot finding for nonlinear function y=f(x) Basic idea for 1-d nonlinear functions Geometrically: uses the secant line to the curve of the nonlinear function to approximate the curve and use the root of the secant line function to approximate the root of the nonlinear function. Avoid computation of derivatives while slow down convergence. Uses secant line between (x0,f(x0 ) and (x1,f(x1 ) to the curve y=f(x) to approximate the tangent line. root (x0,f(x0 ) (x2,f(x2 ) y=f(x ) root x* f(x*)=0 x y (x1,f(x1 ) (x3,f(x3 ) (x4,f(x4 ) Difference quotient approximates derivative It is not convenient to calculate derivatives F(x(k) at each approximate point x(k). Generally, derivatives can be approximated by differences. Discrete Newtons method for nonlinear systemsgeneralization of secant method in n-d Newtons method(vector form) uses the first two terms of Taylor series of F(x) at x(k) to approximate F(x) Component form of Newtons method Linear system with respect to Discrete Newtons method over linearly converges Broydens method for nonlinear systems Broyden,1965 (extension of secant method) Broyden generalizes this formula to nonlinear systems Note the system provides only N equations to determine the NXN matrix. The “best possible” choice for Ak is a minimal modification of Ak-1, e.g., Ak satisfies To avoid computation of derivatives, Broyden uses a matrix Ak satisfying the same formula. once again we are faced with finding an inverse matrix, something we would like to avoid. rather, one can solve and then update Broydens metho

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论