Главная страница


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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 еще про корень...   Kirill Gayduchenko   13 May 2001 20:11:00 
 Re: еще про корень...   Serge Kanilo   15 May 2001 06:02:31 
 еще про корень...   Kirill Gayduchenko   15 May 2001 20:11:26 
 еще про корень...   Ivan Mak   15 May 2001 06:24:14 
 еще про корень...   Kirill Gayduchenko   15 May 2001 20:20:21 
 еще про корень...   Ivan Mak   16 May 2001 06:06:10 
 еще пpо коpень...   Wowa Savin   16 May 2001 11:39:43 
 Re: еще про корень...   Ihor Bobak   15 May 2001 13:17:50 
 еще про корень...   Max Alekseyev   16 May 2001 14:02:54 
 еще пpо коpень...   Wowa Savin   15 May 2001 17:30:23 
 еще про корень...   Igor Dolgov   16 May 2001 03:06:38 
 еще про корень...   Evgenij Masherov   21 May 2001 10:20:46 
Архивное /ru.algorithms/18133b028cfc.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional