9.2. Алгоритм среднеквадратичного приближения функций рациональными дробями

В этом разделе описывается итерационный алгоритм для приближения рациональными дробями, основанный на разработках [111], [115] метода Марквардта Левенберга ([107], [109]) для нелинейных аппроксимирующих функций общего вида. Метод Марквардта-Левенберга является одним из методов для решения нелинейных задач среднеквадратического приближения (см., напр., [30], [46]). В нем делается попытка использовать преимущества метода минимизации

Ньютона посредством учета нелинейности в квадратичной аппроксимации минимизируемой функции без использования вторых производных. Метод Марквардта-Левенберга прост в реализации. Несмотря на то что метод может медленно сходиться на сильно нелинейных задачах, он во многих случаях, как показывает опыт решения прикладных задач большой размерности (см. § 8 гл. III), дает подходящее, с практической точки зрения, приближение за небольшое число итераций.

Постановка задачи

Пусть произвольное множество из состоящее из точек, натуральные числа, На множестве определены функция весовая положительная функция и две линейно-независимые системы функций

Множество рациональных дробей определим как в п. 9.1.1

где

Задача наилучшего среднеквадратического с весом приближения функции рациональными дробями из класса состоит в отыскании дроби на которой реализуется равенство

Решение задачи (9.18) существует не всегда (см., напр., [119], [120], пример в п. 2.1).

Описание алгоритма

Возьмем в качестве нормирующего условия для рациональной дроби условие Обозначим Для удобства дальнейшего изложения перенумеруем коэффициенты начиная с и обозначим через вектор . В новых обозначениях

Пусть вектор коэффициентов (без коэффициента при некоторой дроби полученный на шаге алгоритма. Запишем отрезок ряда Тейлора с точностью до членов 2-го порядка для функции

в окрестности точки

где

то подставляя (9.21)-(9.22) в (9.20), получаем

Заменим в (9.19) дробь отрезком ее ряда Тейлора в точке содержащим только линейные члены

Полученную приближенную формулу для

с учетом запишем в виде

Сравнивая представление из (9.23) с выражением (9.24), которое соответствует замене линейной частью ряда Тейлора, видим, что выражение в правой части (9.23) отличается от (9.24) наличием последней суммы, связанной с нелинейностью Введем следующие обозначения:

диагональная матрица размера с элементами матрица размера

строка матрицы матрицы размера

Исходя из представления функции в виде (9.24), решение зачали (9.18) можно свести к решению следующей последовательности <адач минимизации

где Представление (9.23) позволяет свести решение задачи (9.18) к итерационному решению таких задач:

где

(адача (9.26) в окрестности точки лучше аппроксимирует исходную задачу, чем задача (9.25). Однако функция не является, вообще говоря, выпуклой [79], так что матрица может не быть положительно-определенной, что часто приводит в задаче (9.26) к решению-поправке, не дающей улучшения имеющейся аппроксимации решения задачи (9.18). Стандартный прием, идущий от Марквардта и Левенберга [107], [109] состоит в замене матрицы некоторой положительно-определенной матрицей где некоторое действительное число. При этой замене вместо задачи (9.26) имеем задачу:

В качестве обычно берутся диагональные матрицы с положительными диагональными элементами (напр., в

качестве можно взять соответствующие диагональные элементы матрицы Для таких задачу (9.27) можно переписать так:

Для получения решения задачи (9.28) используется система нормальных уравнений

которую можно решать, например, методом Холецкого [1].

Рассматриваемый метод входит в класс так называемых глобальных квазиньютоновских методов. Подробно такие алгоритмы рассматриваются, например, в [30]. В главах 6, 10 [30] приведены теоремы, дающие условия сходимости таких алгоритмов для минимизируемых функций общего вида. Для некоторых версий алгоритма Марквардта-Левенберга доказана глобальная сходимость (см., напр., [115]).

Вычислительная схема алгоритма

Общая схема алгоритма такова. Пусть начальная рациональная дробь (обычно

Значения параметров, встречающихся в алгоритме, как показывает опыт (см. также [111]), можно задавать такими:

Пусть на шаге найден вектор коэффициентов Формируется система нормальных уравнений (9.29) и ищется по методу Холецкого. Если на некотором шаге метода Холецкого элемент на главной диагонали оказывается близким к нулю, то увеличиваем и решаем систему (9.29) заново. Так повторяем до тех пор, пока либо не найдется численно устойчивого решения, либо не исчерпается допустимое

число повторений. В последнем случае строка и столбец матрицы на пересечении которых диагональный элемент оказывается малым, выбрасываются, соответствующее им значение полагается равным нулю, остальные компоненты вектора вычисляются обычным образом. Путь в результате решения системы (9.29) получен вектор Для каждого вычисляются

во всех точках то полагается Если хотя бы в одной точке то А вычисляется по формуле

Далее, находим номер такой, что в точке достигается минимум

Полагаем и проверяем выполнение условия где выбранная заранее константа, не зависящая от к,

Если условие не выполняется, то в качестве берем значение (т.е. увеличенное в раз) и решаем систему уравнений (9.29) с прежним Если условие выполняется, то берется Проверяется условие окончания счета

Если оно не выполняется, проверяется условие допустимая граница для 7. Если то осуществляется переход к следующей итерации, при этом, если условие (9.30) выполнилось без увеличения и повторного решения системы уравнений, то полагаг иначе берем Если выполняется

условие (9.31) или или, если где К — задаваемое допустимое число итераций, то итерационный процесс считается законченным. Если полученное при этом приближенное решение, не удовлетворяет нужным требованиям, можно решить задачу с новыми или перейти к новому набору базисных функций. Может быть также полезно решить задачу заново с новыми и 70 и в случае, когда решение получено с занулением некоторых

Замечание 2. Из (9.28) видно, что параметром контролируется величина и направление вектора На первых порах итерационного процесса значение целесообразно брать достаточно большим, т. к. такие у к не позволяют компонентам вектора быть большими. Обоснованию этого утверждения могут служить следующие соображения: начальная рациональная дробь, как правило, далека от наилучшей, аппроксимация (9.28) задачи (9.18) достаточно плохая, поэтому сравнительно малые компоненты обеспечивают лучшее убывание а также облегчают сохранение положительности знаменателя. Отметим еще одну особенность аппроксимации (9.28) задачи (9.18). На первых итерациях матрица в соотношении (9.29) часто бывает плохо обусловленной, в частности, дробь которая обычно берется в качестве начальной из-за отсутствия априорной информации об искомой дроби, влечет линейную зависимость векторов матрицы Положительная определенность (и соответственно обусловленность) матрицы системы нормальных уравнений обеспечивается выбором параметра

Замечание 3. Малые у к способствуют более быстрой сходимости алгоритма, однако может оказаться предпочтительнее вместо малых брать малое значение а, чтобы было легче удовлетворить условию (9.30).

Замечание 4. Улучшению устойчивости системы нормальных уравнений способствует следующая обработка исходных данных: преобразование независимых переменных по формуле где диагональная матрица с элементами а во многих случаях и масштабирование значений так, чтобы значения преобразованной функции по модулю были соизмеримы со значениями аргумента.