Поиск корней липшицируемой функции с известной константой Липшица

Метод ищет корень уравнения f(x) = 0, расположенный на отрезке [a, b], причем функция f - липшицируема на отрезке [a, b] с известной константой Липшица. Функция называется липшицируемой на [a, b], если существует такое наименьшее число L (константа Липшица), что для любых x, y из [a, b] верно неравенство |f(x)-f(y)| <= L*|x-y|.

Немного о липщицируемости. Любая липшицируемая функция непрерывна, но обратное не верно (скажем, функция y = x ^0.5 на отрезке [0, 1]. Достаточным условием липшицируемости является существование ограниченной непрерывной производной. Константа Липшища зависит как от выбранной функции, так и от выбранного отрезка. Если константа неизвестна, то можно взять число, которое гарантированно больше её.

Идея метода заключается в том, что зная константу Липшица и значение функции в некоторой точке, можно точно сказать, на каком отрезке гарантированно нет корней. В самом деле, пусть в точке x функция принимает значение f(x), а в точке y принимает значение f(y) = 0. Подставив значения в условие Липшица, получаем |x-y| >= |f(x)|/L. Т.е. существует целая окрестность точки x, в которой гарантированно нет корней.

Следует отметить, что алгоритм несколько отличается от других методов поиска корней. Во-первых, он требует не только липшицируемости функции, но и знания константы Липшица (или её оценки сверху). Во-вторых, алгоритм не отличается высокой скоростью сходимости в случае кратных корней или сильно завышенной константы Липшица. В-третьих, алгоритм не дает никаких сведений о существовании корней - он просто ищет точки с достаточно малым значением модуля функции. Если на вашем отрезке есть корни, то для любого epsilon алгоритм гарантированно найдет точку, в которой значение функции меньше epsilon. Если корней нет, но такие точки существуют, то алгоритм иногда всё же может обнаружить такие точки.

Если нашли ошибку в алгоритме - сообщите!

Реализации алгоритма на различных языках:

Реализация алгоритма на AlgoPascal:

unit LipshitzRootUnit;

declaration
    function F(X:Real):Real;
interface
    LipshitzFindRoot;
implementation

(***********************************************************
Приближенный поиск корней липшицируемой функции.

Подпрограмма позволяет приближенно найти корни липшицируемой
функции, расположенные на отрезке [A,B].
Если на отрезке [A,B] есть  корни,  то  подпрограмма  всегда
возвращает одну из точек, в которой значение функции  меньше
Epsilon. Если на отрезке корней нет но есть точки, в которых
функция по модулю  меньше  Epsilon, то  подпрограмма   может
сойтись к одной из таких точек, а может и не сойтись.

Параметры:
    A, B        - отрезок для поиска.
    FA, FB      - значения функции на концах отрезка
    L           - константа Липшица для данной функции    на
                  данном отрезке. L>0.
    Epsilon     - ограничение на модуль функции
    Root        - содержит точку, если функция вернула True.
Результат:
    Если функция вернула True, то в переменной Root находится
точка. Иначе на отрезке искомых точек нет (для данного Epsilon).
***********************************************************)
function LipshitzFindRoot(
    const   A       :   Real;
    const   B       :   Real;
    const   FA      :   Real;
    const   FB      :   Real;
    const   L       :   Real;
    const   Epsilon :   Real;
    out     Root    :   Real):Boolean;
var
    DA      :   Real;
    DB      :   Real;
    M       :   Real;
    FM      :   Real;
    Delta   :   Real;
begin
    Delta := Epsilon/L;
    
    //если A или B - корень
    if AbsReal(FA)<Epsilon then
    begin
        Result:=True;
        Root:=A;
        Exit;
    end;
    if AbsReal(FB)<Epsilon then
    begin
        Result:=True;
        Root:=B;
        Exit;
    end;

    //если отрезок слишком мал
    if B-A<Delta then
    begin
        Result:=False;
        Exit;
    end;
    
    //проверим, могут ли в принципе быть корни
    DA:=A+(AbsReal(FA)-Epsilon)/L;
    DB:=B-(AbsReal(FB)-Epsilon)/L;
    if DA>DB then
    begin
        Result:=False;
        Exit;
    end;
    
    //делим отрезок пополам, ищем в центре
    M:=(DA+DB)/2;
    FM:=F(M);
    if AbsReal(FM)<Epsilon then
    begin
        Result:=True;
        Root:=M;
        Exit;
    end;

    //ищем на первой половине
    if LipshitzFindRoot(A,M,FA,FM,L,Epsilon,Root) then
    begin
        Result:=True;
        Exit;
    end;

    //ищем на второй половине
    if LipshitzFindRoot(M,B,FM,FB,L,Epsilon,Root) then
    begin
        Result:=True;
        Exit;
    end;

    Result:=False;
end;


end.

Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU