任何人都看到我的牛顿方法有任何问题&改性？ [英] anybody see any problems with my newtons method & modified?
本文介绍了任何人都看到我的牛顿方法有任何问题&改性？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我不确定我做错了什么。修改后应该更快收敛。尝试更大的迭代时遇到了同样的问题。
这是我原来的：
I am unsure what I have done wrong. The modified should definitely converge faster. I had the same issues trying larger iterations.
Here is my original:
#include <stdio.h>
#include <math.h>
double f(double x)
{
//return (x*x-6);
//return (x*x*x-2*x*x-5);
//return (x*x-2*x*exp(-1*x)+exp(-2*x));
return (cos(x+sqrt(2))+x*((x/2)+sqrt(2)));
}
double fp(double x)
{
//return (2*x);
//return (3*x*x-4*x);
//return (2*x+2*x*exp(-1*x)-2*exp(-1*x)-2*exp(-2*x));
return (x-sin(x+sqrt(2))+sqrt(2));
}
int main()
{
double p0, TOL, p;
int i=1, N0;
printf("Initial approximation: ");
scanf("%lf", &p0);
printf("Desired Tolerance: ");
scanf("%lf", &TOL);
printf("Maximum number of iterations: ");
scanf("%d", &N0);
while(i<=N0)
{
p=p0-(f(p0)/fp(p0));
if((fabs(p-p0)) < TOL)
{
printf("Iteration: %d. Current value= %lf.", i, p);
}
i++;
p0=p;
}
if(i>N0)
printf("Method failed after %d iterations.", N0);
}
结果：
Results:
Initial approximation: -1.5
Desired Tolerance: .01
Maximum number of iterations: 100
Iteration: 2. Current value= -1.414242.Iteration: 3. Current value= -1.414251.
Iteration: 4. Current value= -1.414263.Iteration: 5. Current value= -1.414280.
Iteration: 6. Current value= -1.414302.Iteration: 7. Current value= -1.414331.
Iteration: 8. Current value= -1.414368.Iteration: 9. Current value= -1.414404.
Iteration: 10. Current value= -1.414444.Iteration: 11. Current value= -1.41444
5.Iteration: 12. Current value= -1.414462.Iteration: 13. Current value= -1.414
457.Iteration: 14. Current value= -1.414463.Iteration: 15. Current value= -1.4
14442.Iteration: 16. Current value= -1.414447.Iteration: 17. Current value= -1
.414442.Iteration: 18. Current value= -1.414457.Iteration: 19. Current value=
-1.414436.Iteration: 20. Current value= -1.414444.Iteration: 21. Current value
= -1.414461.Iteration: 22. Current value= -1.414450.Iteration: 23. Current val
ue= -1.414452.Iteration: 24. Current value= -1.414448.Iteration: 25. Current v
alue= -1.414459.Iteration: 26. Current value= -1.414460.Iteration: 27. Current
value= -1.414469.Iteration: 28. Current value= -1.414438.Iteration: 29. Curre
nt value= -1.414442.Iteration: 30. Current value= -1.414439.Iteration: 31. Cur
rent value= -1.414465.Iteration: 32. Current value= -1.414448.Iteration: 33. C
urrent value= -1.414448.Iteration: 34. Current value= -1.414434.Iteration: 35.
Current value= -1.414455.Iteration: 36. Current value= -1.414469.Iteration: 37
. Current value= -1.414435.Iteration: 38. Current value= -1.414459.Iteration:
39. Current value= -1.414442.Iteration: 40. Current value= -1.414466.Iteration
: 41. Current value= -1.414441.Iteration: 42. Current value= -1.414456.Iterati
on: 43. Current value= -1.414442.Iteration: 44. Current value= -1.414424.Itera
tion: 45. Current value= -1.414454.Iteration: 46. Current value= -1.414466.Ite
ration: 47. Current value= -1.414413.Iteration: 48. Current value= -1.414441.I
teration: 49. Current value= -1.414437.Iteration: 50. Current value= -1.414457
.Iteration: 51. Current value= -1.414462.Iteration: 52. Current value= -1.4144
62.Iteration: 53. Current value= -1.414457.Iteration: 54. Current value= -1.41
4446.Iteration: 55. Current value= -1.414454.Iteration: 56. Current value= -1.
414466.Iteration: 57. Current value= -1.414460.Iteration: 58. Current value= -
1.414468.Iteration: 59. Current value= -1.414460.Iteration: 60. Current value=
-1.414434.Iteration: 61. Current value= -1.414436.Iteration: 62. Current valu
e= -1.414438.Iteration: 63. Current value= -1.414432.Iteration: 64. Current va
lue= -1.414435.Iteration: 65. Current value= -1.414436.Iteration: 66. Current
value= -1.414449.Iteration: 67. Current value= -1.414468.Iteration: 68. Curren
t value= -1.414468.Iteration: 69. Current value= -1.414448.Iteration: 70. Curr
ent value= -1.414467.Iteration: 71. Current value= -1.414466.Iteration: 72. Cu
rrent value= -1.414456.Iteration: 73. Current value= -1.414470.Iteration: 74.
Current value= -1.414437.Iteration: 75. Current value= -1.414439.Iteration: 76.
Current value= -1.414456.Iteration: 77. Current value= -1.414434.Iteration: 7
8. Current value= -1.414427.Iteration: 79. Current value= -1.414426.Iteration:
80. Current value= -1.414460.Iteration: 81. Current value= -1.414465.Iteratio
n: 82. Current value= -1.414420.Iteration: 83. Current value= -1.414456.Iterat
ion: 84. Current value= -1.414456.Iteration: 85. Current value= -1.414469.Iter
ation: 86. Current value= -1.414468.Iteration: 87. Current value= -1.414447.It
eration: 88. Current value= -1.414422.Iteration: 89. Current value= -1.414448.
Iteration: 90. Current value= -1.414442.Iteration: 91. Current value= -1.41445
1.Iteration: 92. Current value= -1.414464.Iteration: 93. Current value= -1.414
466.Iteration: 94. Current value= -1.414417.Iteration: 95. Current value= -1.4
14444.Iteration: 96. Current value= -1.414429.Iteration: 97. Current value= -1
.414453.Iteration: 98. Current value= -1.414434.Iteration: 99. Current value=
-1.414438.Iteration: 100. Current value= -1.414436.Method failed after 100 iter
ations.
Process returned 35 (0x23) execution time : 8.484 s
Press any key to continue.
这是修改过的牛顿：
Here is the modified Newtons:
#include <stdio.h>
#include <math.h>
double f(double x)
{
//return (x*x-2*x*exp(-1*x)+exp(-2*x));
return (cos(x+sqrt(2))+x*((x/2)+sqrt(2)));
}
double fp(double x)
{
//return (2*x+2*x*exp(-1*x)-2*exp(-1*x)-2*exp(-2*x));
return (x-sin(x+sqrt(2))+sqrt(2));
}
double fpp(double x)
{
//return (2-2*x*exp(-1*x)+4*exp(-1*x)+4*exp(-2*x));
return (1-cos(x+sqrt(2)));
}
int main()
{
double p0, TOL, p;
int i=1, N0;
printf("Initial approximation: ");
scanf("%lf", &p0);
printf("Desired Tolerance: ");
scanf("%lf", &TOL);
printf("Maximum number of iterations: ");
scanf("%d", &N0);
while(i<=N0)
{
p=p0-((f(p0)*fp(p0))/(pow(fp(p0),2)-f(p0)*fpp(p0)));
if((fabs(p-p0)) < TOL)
{
printf("Iteration: %d. Current value= %lf.", i, p);
}
i++;
p0=p;
}
if(i>N0)
printf("Method failed after %d iterations.", N0);
}
Results:
Results:
Initial approximation: -1.5
Desired Tolerance: .01
Maximum number of iterations: 100
Iteration: 2. Current value= -1.414242.Iteration: 3. Current value= -1.414251.
Iteration: 4. Current value= -1.414263.Iteration: 5. Current value= -1.414280.
Iteration: 6. Current value= -1.414302.Iteration: 7. Current value= -1.414331.
Iteration: 8. Current value= -1.414368.Iteration: 9. Current value= -1.414404.
Iteration: 10. Current value= -1.414444.Iteration: 11. Current value= -1.41444
5.Iteration: 12. Current value= -1.414462.Iteration: 13. Current value= -1.414
457.Iteration: 14. Current value= -1.414463.Iteration: 15. Current value= -1.4
14442.Iteration: 16. Current value= -1.414447.Iteration: 17. Current value= -1
.414442.Iteration: 18. Current value= -1.414457.Iteration: 19. Current value=
-1.414436.Iteration: 20. Current value= -1.414444.Iteration: 21. Current value
= -1.414461.Iteration: 22. Current value= -1.414450.Iteration: 23. Current val
ue= -1.414452.Iteration: 24. Current value= -1.414448.Iteration: 25. Current v
alue= -1.414459.Iteration: 26. Current value= -1.414460.Iteration: 27. Current
value= -1.414469.Iteration: 28. Current value= -1.414438.Iteration: 29. Curre
nt value= -1.414442.Iteration: 30. Current value= -1.414439.Iteration: 31. Cur
rent value= -1.414465.Iteration: 32. Current value= -1.414448.Iteration: 33. C
urrent value= -1.414448.Iteration: 34. Current value= -1.414434.Iteration: 35.
Current value= -1.414455.Iteration: 36. Current value= -1.414469.Iteration: 37
. Current value= -1.414435.Iteration: 38. Current value= -1.414459.Iteration:
39. Current value= -1.414442.Iteration: 40. Current value= -1.414466.Iteration
: 41. Current value= -1.414441.Iteration: 42. Current value= -1.414456.Iterati
on: 43. Current value= -1.414442.Iteration: 44. Current value= -1.414424.Itera
tion: 45. Current value= -1.414454.Iteration: 46. Current value= -1.414466.Ite
ration: 47. Current value= -1.414413.Iteration: 48. Current value= -1.414441.I
teration: 49. Current value= -1.414437.Iteration: 50. Current value= -1.414457
.Iteration: 51. Current value= -1.414462.Iteration: 52. Current value= -1.4144
62.Iteration: 53. Current value= -1.414457.Iteration: 54. Current value= -1.41
4446.Iteration: 55. Current value= -1.414454.Iteration: 56. Current value= -1.
414466.Iteration: 57. Current value= -1.414460.Iteration: 58. Current value= -
1.414468.Iteration: 59. Current value= -1.414460.Iteration: 60. Current value=
-1.414434.Iteration: 61. Current value= -1.414436.Iteration: 62. Current valu
e= -1.414438.Iteration: 63. Current value= -1.414432.Iteration: 64. Current va
lue= -1.414435.Iteration: 65. Current value= -1.414436.Iteration: 66. Current
value= -1.414449.Iteration: 67. Current value= -1.414468.Iteration: 68. Curren
t value= -1.414468.Iteration: 69. Current value= -1.414448.Iteration: 70. Curr
ent value= -1.414467.Iteration: 71. Current value= -1.414466.Iteration: 72. Cu
rrent value= -1.414456.Iteration: 73. Current value= -1.414470.Iteration: 74.
Current value= -1.414437.Iteration: 75. Current value= -1.414439.Iteration: 76.
Current value= -1.414456.Iteration: 77. Current value= -1.414434.Iteration: 7
8. Current value= -1.414427.Iteration: 79. Current value= -1.414426.Iteration:
80. Current value= -1.414460.Iteration: 81. Current value= -1.414465.Iteratio
n: 82. Current value= -1.414420.Iteration: 83. Current value= -1.414456.Iterat
ion: 84. Current value= -1.414456.Iteration: 85. Current value= -1.414469.Iter
ation: 86. Current value= -1.414468.Iteration: 87. Current value= -1.414447.It
eration: 88. Current value= -1.414422.Iteration: 89. Current value= -1.414448.
Iteration: 90. Current value= -1.414442.Iteration: 91. Current value= -1.41445
1.Iteration: 92. Current value= -1.414464.Iteration: 93. Current value= -1.414
466.Iteration: 94. Current value= -1.414417.Iteration: 95. Current value= -1.4
14444.Iteration: 96. Current value= -1.414429.Iteration: 97. Current value= -1
.414453.Iteration: 98. Current value= -1.414434.Iteration: 99. Current value=
-1.414438.Iteration: 100. Current value= -1.414436.Method failed after 100 iter
ations.
Process returned 35 (0x23) execution time : 8.484 s
Press any key to continue.推荐答案
Apart from your failure to recognize convergence, there is a more severe problem with your code: you don’t test for 0 or near-0 values when calculating the next step and performing divisions, i.即in the simple newton method you should test fp for 0 (or near-0) before dividing.
The problem in question is very ill conditioned, meaning that it it is prone to convergence problems due to rounding effects. It’s likely the problem was deliberately set up this way to make you aware of these potential problems, so I won’t spoil your experience by going into more detail. But I would advise you to do the following:
1. Change your print-out to show the curent value of p at every step of the iteration, even before it has converged. Please do add a linebreak at the end, too - it will help!
2. Along with the current value of p, also print out the value of the function f(p). f(p) should converge to 0, so it’s easier to judge the quality of the current guess
3. Fix the loop to exit after convergence, as suggested in solution 1
4. Try out very small tolerance values (try repeatedly with ever shrinking values). Take note how you’ll eventually reach a point where the iteration simply doesn’t improve, or even gets significantly worse.
P.S.:
There are many ways to control an iterative numerical algorithm such as the newton method:
1. number of steps: this will always work, and is a good way to prevent endless loops or detect convergence issues.
2. difference of function value to target value (0 in this case): you don’t check this here - why? That is the central goal here!
3. relative improvement, i.即how much has the result (obtained from 2.) improved compared to the last step, or couple of last steps?
4. relative step size, i.即how much (or, rather, how little) is the argument being changed compared to the last step - this is what you test; consider that this step size does not in fact indicate your progress (or lack thereof) towards a better solution! To judge that, see 2. and 3. above!
5. history of steps: when you keep stepping back and forth (as you can see in your results from about iteration 15) without any progress (which you can measure by looking at f(p)), then your algorithm is stuck!
The importance of implementing convergance criteria is pretty much in the order as they are listed here: the first is just a safeguard in case the others don’t catch a problem. The second is measuring what you’re trying to accomplish. The 3rd and 4th are really only needed to keep the calculations in a range where rounding errors (hopefully) won’t influence the algorithm. And the 5th (and possibly other tests) is there to catch the really odd corner cases where your chosen algorithm simply doesn’t work as expected.
P.P.S.:
Just to get an impression about things you need to consider when programming a foolproof rootfinder that always delivers a right answer, google for Jack Crenshaws \"The Worlds Best Rootfinder\" or just look it up on www.embedded.com[^]. You’ll find a series of about 6 articles spread out over the course of several years where Crenshaw describes how he went to implement a rootfinder that is efficient, but also capable to deal with every conceivable corner case that it might encounter.
It’s also very enlightening how, over the time, Crenshaw came to consider specific cases that he didn’t think of at first. Even if you have difficulties following the math involved there, I encourage you to take a look!
Funnily, \"TWBRF\" wouldn’t help here, as it’s core assumption is a true root, i.即a function that passes from negative to positive values or vice versa, whereas your example has a local minimum in it’s root.
Apart from your failure to recognize convergence, there is a more severe problem with your code: you don't test for 0 or near-0 values when calculating the next step and performing divisions, i. e. in the simple newton method you should test fp for 0 (or near-0) before dividing.
The problem in question is very ill conditioned, meaning that it it is prone to convergence problems due to rounding effects. It's likely the problem was deliberately set up this way to make you aware of these potential problems, so I won't spoil your experience by going into more detail. But I would advise you to do the following:
1. Change your print-out to show the curent value of p at every step of the iteration, even before it has converged. Please do add a linebreak at the end, too - it will help!
2. Along with the current value of p, also print out the value of the function f(p). f(p) should converge to 0, so it's easier to judge the quality of the current guess
3. Fix the loop to exit after convergence, as suggested in solution 1
4. Try out very small tolerance values (try repeatedly with ever shrinking values). Take note how you'll eventually reach a point where the iteration simply doesn't improve, or even gets significantly worse.
P.S.:
There are many ways to control an iterative numerical algorithm such as the newton method:
1. number of steps: this will always work, and is a good way to prevent endless loops or detect convergence issues.
2. difference of function value to target value (0 in this case): you don't check this here - why? That is the central goal here!
3. relative improvement, i. e. how much has the result (obtained from 2.) improved compared to the last step, or couple of last steps?
4. relative step size, i. e. how much (or, rather, how little) is the argument being changed compared to the last step - this is what you test; consider that this step size does not in fact indicate your progress (or lack thereof) towards a better solution! To judge that, see 2. and 3. above!
5. history of steps: when you keep stepping back and forth (as you can see in your results from about iteration 15) without any progress (which you can measure by looking at f(p)), then your algorithm is stuck!
The importance of implementing convergance criteria is pretty much in the order as they are listed here: the first is just a safeguard in case the others don't catch a problem. The second is measuring what you're trying to accomplish. The 3rd and 4th are really only needed to keep the calculations in a range where rounding errors (hopefully) won't influence the algorithm. And the 5th (and possibly other tests) is there to catch the really odd corner cases where your chosen algorithm simply doesn't work as expected.
P.P.S.:
Just to get an impression about things you need to consider when programming a foolproof rootfinder that always delivers a right answer, google for Jack Crenshaws "The Worlds Best Rootfinder" or just look it up on www.embedded.com[^]. You'll find a series of about 6 articles spread out over the course of several years where Crenshaw describes how he went to implement a rootfinder that is efficient, but also capable to deal with every conceivable corner case that it might encounter.
It's also very enlightening how, over the time, Crenshaw came to consider specific cases that he didn't think of at first. Even if you have difficulties following the math involved there, I encourage you to take a look!
Funnily, "TWBRF" wouldn't help here, as it's core assumption is a true root, i. e. a function that passes from negative to positive values or vice versa, whereas your example has a local minimum in it's root.
first, you don’t break the iteration when diff falls into the tolerance value. therefore, you end up with ’i>NO’. convert to that
first, you don't break the iteration when diff falls into the tolerance value. therefore, you end up with 'i>NO'. convert to that
printf("Iteration: %d. Current value= %lf.", i, p);
if((fabs(p-p0)) < TOL)
{
break;
}
secondly, I think you forgot to compile one of your codes before pasting output into the question. both outputs are the same, which is not expected.
third, tolerance value is too big. you may get a better output with 0.0001 since the root is about -1.4144.
last, could you provide a website for the proof of the second approximation? (this part is for me. please? :) )
secondly, I think you forgot to compile one of your codes before pasting output into the question. both outputs are the same, which is not expected.
third, tolerance value is too big. you may get a better output with 0.0001 since the root is about -1.4144.
last, could you provide a website for the proof of the second approximation? (this part is for me. please? :) )
这篇关于任何人都看到我的牛顿方法有任何问题&改性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
