[郑重声明],本文大量引用了维基百科内容。
这里主要以简单的牛顿迭代法介绍非线性方程的求解,维基百科对“牛顿迭代法”的解释:
Newton's method From Wikipedia, the free encyclopedia Jump to navigationJump to search This article is about Newton's method for finding roots. For Newton's method for finding minima, see Newton's method in optimization. In numerical analysis, Newton's method (also known as the Newton–Raphson method), named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots (or zeroes) of a real-valued function. It is one example of a root-finding algorithm. 关于未知量x的非线性方程:f(x)=0 The Newton–Raphson method in one variable is implemented as follows: The method starts with a function f defined over the real numbers x, the function's derivative f ′, and an initial guess x0 for a root of the function f. If the function satisfies the assumptions made in the derivation of the formula and the initial guess is close, then a better approximation x1 is
Geometrically, (x1, 0) is the intersection of the x-axis and the tangent of the graph of f at (x0, f (x0)). The process is repeated as
until a sufficiently accurate value is reached. 维基百科的例子:Examples Square root of a number Consider the problem of finding the square root of a number. Newton's method is one of many methods of computing square roots. For example, if one wishes to find the square root of 612, this is equivalent to finding the solution to
The function to use in Newton's method is then f(x)=x^2-612 with derivative
With an initial guess of 10, the sequence given by Newton's method is
here the correct digits are underlined. With only a few iterations one can obtain a solution accurate to many decimal places.
牛顿法就是一种迭代求解非线性方程的方法。
好了,我们自己动手实现牛顿迭代法吧。我们求解方程2*x=exp(-x)的解吧。这个函数的定义在js中是:
1. var Fun=function(x){ //函数
2. return (2*x - Math.exp(-x));
3. }
我们知道牛顿迭代法有一个缺点,求根必须已知其导数,这就限制了牛顿迭代法的应用范围。however,我们定义它的导数:
1. var diffFun=function(x){ //导数
2. return (2 + Math.exp(-x));
3. }
根据前面的迭代公式,我们定义迭代函数,这个函数给一个初始值x,返回一个新的根:
1. var iterate=function(x){ //牛顿迭代函数
2. return (x - Fun(x) / diffFun(x));
3. }
好了,给出整个计算流程了:
1. var x1,err,x0 =0.5; //迭代初值x0
2. var tol = 0.00001; //求解精度tol
3. var iter =0,iterMax=100,residual; //iter迭代次数,iterMax为最大迭代次数
4.
5. do{
6. iter++;
7. x1= iterate(x0);//执行迭代
8. err= Math.abs(x1 - x0);//计算两次迭代偏差
9. console.log("迭代次数:",iter,"/最新迭代结果:",x1,"/与上次结果差值:",err);
10. x0= x1;//更新初始值
11. }while(err >= tol && iter < iterMax);//满足精度要求,迭代结束
12.
13. if(iter <iterMax){
14. console.log("方程最终解:",x1);
15. residual=Fun(x1);
16. console.log("残差为:",residual);
17. }
18. else
19. console.log("迭代求解失败!");
祭出整个html文档:
1. <!DOCTYPEhtml>
2. <htmlstyle="height: 100%">
3. <head>
4. <metacharset="utf-8">
5. </head>
6. <bodystyle="height: 100%; margin: 0">
7. <divid="container" style="height: 100%"></div>
8. <scripttype="text/javascript">
9.
10. var Fun=function(x){ //函数
11. return (2*x - Math.exp(-x));
12. }
13.
14. var diffFun=function(x){ //导数
15. return (2 + Math.exp(-x));
16. }
17.
18. var iterate=function(x){ //牛顿迭代函数
19. return (x - Fun(x) / diffFun(x));
20. }
21.
22. var x1,err,x0 =0.5; //迭代初值x0
23. var tol = 0.00001; //求解精度tol
24. var iter =0,iterMax=100,residual; //迭代次数
25.
26. do{
27. iter++;
28. x1= iterate(x0);
29. err= Math.abs(x1 - x0);
30. console.log("迭代次数:",iter,"/最新迭代结果:",x1,"/与上次结果差值:",err);
31. x0= x1;
32. }while(err >= tol && iter < iterMax);
33.
34. if(iter <iterMax){
35. console.log("方程最终解:",x1);
36. residual=Fun(x1);
37. console.log("残差为:",residual);
38. }
39. else
40. console.log("迭代求解失败!");
41.
42. </script>
43. </body>
44. </html>
点击html运行网页:
查看结果:
要注意的是,最后残差并不一定是真正的残差,需要看程序浮点数的位数,比如C语言单精度浮点数有效位数是6-7位,如果计算得到残差为-10次方,那肯定不可信。
实际上,本文所讲的牛顿迭代法在实际科研中应用不多,因为很多时候并不能求解得到有效根。有兴趣的同学可以学习Matlab中的fsolve函数,或者python的科学计算包scipy中的一系列非线性函数求解。