Статья Автор: Лебедев Дмитрий

Метод "чисел Фибоначчи" для решения уравнения

Постановка задачи.
Необходимо найти корень уравнения f(x)=0 на целевом отрезке [L;R].
Известно, что f(L) < 0 < f(R) и для любого рационального числа  x  можно определить знак f(x).
Корень уравнения надо найти с большой точностью и в формате рационального числа.

Для поиска корня можно применить бинарный поиск с рациональными числами,
но знаменатель дроби будет очень быстро расти и могут возникнуть сложности.
Более перспективным выглядит тернарный поиск (будем искать минимум abs(f(x)) с использованием метода "чисел Фибоначчи".
Проблема состоит в том, что для тернарного поиска используется значение функции, а это может ограничить точность вычисления корня.  
 

Рассмотрим пример \(x^2+\sqrt{x}\ =\ C\) 
Будем использовать целевую функцию \(f(x)=x^2+\sqrt{x}\ -\ C\) и целевой интервал [0,C] 
Нетрудно убедиться, что при \(C>0\ f(0)\ <\ 0 < f(C)\)
 Найдем решения различными способами. 
Точность будем определять количеством выполнения шагов алгоритма.
1. Бинарный поиск по вещественному значению
 


2. Бинарный поиск с использованием модуля fractions (рациональные числа)
Запустив программу для разных значений C можно увидеть, что точность вычислений "не останавливается", но знаменатель решения очень большие


3. Для получения среднего значения можно попробовать "правило средней скорости"  \(если\ \frac{a}{b}\ < \ \frac{c}{d}\ ,\ то\ \frac{a}{b}\ < \ \frac{a+c}{b+d}\ < \ \frac{c}{d}\ \)
Запустив программу для разных C. Заметим, что знаменатели стали меньше, но и точность вычислений стала хуже.
Это вызвано тем, что для эффективного решения нужна "соизмериность" знаменателей границ целевого отрезка.
 


4. Тернарный поиск предназначен для поиска локального экстремума, то есть "неизвестного" значения функции.
Однако, если брать модуль целевой функции, то тернарный поиск можно использовать для поиска корней уравнения.  
Используем тернарный поиск с методом "чисел Фибоначчи" используя значения функции.
 


5. Модифицируем методом "чисел фибоначчи" для поиска по знаку функции.
На каждом шаге получаются x1, x2 и отбрасывается одно из значений L или R
Выбор делается на основании значения неравенства f(x1) > f(x2)
В случае использования знака функции легко заметить, что
из  f(x2) ==  -1 следует, f(x1)<0 и можно "отбрасывать" значение L
из  f(x1) ==  1 следует, f(x2)<0 и можно "отбрасывать" значение R
если оба условия не выполнены, то есть  f(x1) < 0 < f(x2), то можно отбрасывать любое из L, R


 


Подведем итоги.
  1.  Наибольшую точность дает обычный бинарный поиск с использованием модуля fractions и определением знака целевой функции
  2. Тернарный поиск можно использовать для поиска решения уравнения монотонной функции.
    Для этого лучше использовать метод "чисел Фибоначчи", модуль fractions и определение знака функции. 
    Для достижения результата, сравнимого с бинарным поиском нужно делать примерно в 1,5 раза больше шагов
  3.  Использование бинарного поиска с получением среднего по правилу "средней скорости"  (\(если\ \frac{a}{b}\ < \ \frac{c}{d}\ ,\ то\ \frac{a}{b}\ < \ \frac{a+c}{b+d}\ < \ \frac{c}{d}\ \))
    дает результат с "малыми" значениями знаменателя и может быть хорошей альтернативой бинарному поиску со средним арифметическим.

      
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать