|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Max Alekseyev 2:5015/60 16 May 2001 14:02:54 To : Ihor Bobak Subject : еще про корень... -------------------------------------------------------------------------------- ЫЫЫЫ OS/2 Hi, Ihor ! Replying to a message of Ihor Bobak to All: IB> Попробуй приблизить цепными дробями. IB> sqrt(c) = sqrt(a^2 + b) = IB> = a + b IB> -------------- IB> 2*a + b IB> ------------- IB> 2*a + b IB> ----------- IB> 2*a + IB> .... IB> Раскласть с^2 на сумму a^2 + b ты сможешь, IB> а потом найди несколько приближений цепной дроби IB> (она в несколько раз быстрее сходится чем Маклорен или Тейлор, IB> итераций будет нужно меньше). Эта цепная дробь в классическом виде выглядит как [a;2a/b,2a,2a/b,2a,...] Hетрудно проверить, что числители и знаменатели ее подходящих дробей удовлетворяют рекуррентному соотношению u_{n+4} = (4a^2/b + 2) u_{n+2} - u_n Рассматривая характеристическое уравнение этого соотношения получим, что его решения асимптотически растут как C*k^(n/2), где k=2a^2/b+1+2a*sqrt(a^2/b^2+1/b) ~= 4a^2/b, C - некоторая постоянная. Применяя известную теорему о точности приближения подходящими дробями получим, что n-я подходящая дробь рассматриваемой цепной дроби приближает искомый корень с точностью порядка C/k^n. К чему это я? Да к тому, что классический метод Hьютона реализуемый в данном случае формулой t_{n+1} = (t_n + c/t_n)/2 дает значительно лучшие результаты: на каждом шаге он удваивает точность, т.е. t_n будет отличаться от sqrt(c) не более чем на C/s^(2^n), где C и s>1 - некоторые константы. В действительности, s^(2^n) растет _значительно_ быстрее k^n. Regards, ш.ш Max ~ --- OS/2 Uptime: 0d 17h 34m 20s 351ms * Origin: OS/2 любят, а с Windows - трахаются. (2:5015/60) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/18133b028cfc.html, оценка из 5, голосов 10
|