1632
правки
Изменения
м
'''int''' r = x2
'''int''' l = x1
'''while''' abs(r - l) > < eps '''return''' (x1 + x2) / 2 ===Ошибки псевдокода===1. Используются вычислительно-неустойчивые формулы.2. Учитывается только абсолютная длина отрезка.Подробнее:http://mech.math.msu.su/~iliagri/zip/sem2book.pdf
rollbackEdits.php mass rollback
==Алгоритм==
===МотивацияОбоснование===
Рассмотрим одну итерацию алгоритма [[Троичный поиск|троичного поиска]]. Попробуем подобрать такое разбиение отрезка на три части, чтобы на следующей итерации одна из точек нового разбиения совпала с одной из точек текущего разбиения. Тогда в следующий раз не придется считать функцию в двух точках, так как в одной она уже была посчитана.
<tex> \dfrac{a + b}{c} = \dfrac{b + c}{a} = \varphi </tex>
Расстояние от <tex>l</tex> до <tex>x1 = a + b - c = a' </tex>, от <tex>x2 </tex> до <tex> r = b = c'</tex>, от <tex>х1 </tex> до <tex> х2 = c - b = b'</tex>. Т.е. если мы подставим <tex>a', b', c'</tex> в старое соотношение <tex> \dfrac{a + b}{c} </tex>, то получится <tex> \dfrac {a + b - c + c - b}{b} = \dfrac{a}{b}</tex>.
<tex> \dfrac{a}{b} = \varphi </tex>
===Псевдокод===
'''intdouble''' goldenSectionSearch(f: '''intdouble -> double''' f, l: '''intdouble''' l, r: '''intdouble''' r, eps: '''intdouble''' eps): '''double''' phi = (1 + sqrt(5)) / 2 '''double''' resphi = 2 - phi '''double''' x1 = l + resphi * (r - l) '''int''' x2 = r - resphi * (r - l) '''int''' f1 = f(x1) '''int''' f2 = f(x2)
'''do'''
'''if''' f1 < f2
x2 = x1
f2 = f1
f1 = f(x1)
'''else'''
x1 = x2
f1 = f2
x2 = r - resphi * (r - l)
f2 = f(x2)
==Время работы==
