1.2.3. Метод Ньютона по параметру

Метод Ньютона по параметру относится к классу квазиньюто­новских методов и предусматривает расчет нового исходного прибли­жения по формуле

_,

где — параметр, выбираемый на каждой итерации.

При — 1 метод совпадает с обычным методом Ньютона.

Параметр выбирают с целью ускорения сходимости и преду­преждения расходимости метода. Факт расходимости может быть установлен, если невязка любого уравнения системы не умень­шилась по сравнению с предыдущей итерацией.

Метод Бройдена предусматривает выбор параметра в про­цессе поиска по направлению вектора поправок минимума од­ной из норм вектора невязок, например, евклидовой:

В простейшем случае можно попытаться выполнить последова­тельность расчетов Ф(Х), уменьшая шаг вдвое, т.е. полагая 0.5,0-25,... пока Ф(Х) не уменьшитсяили не станет малой ве­личиной. Более сложные варианты предусматривают аппроксимациюсечения по направлению поверхности функции невязок выпук­лой квадратичной функцией и выбор , обеспечивающего минимум этой функции.

Вычислим значение Ф₀ и, выполнив предварительно шаг метода Ньютона, вычислим Если , то поиск на отрезке [0,1] начи­нается с α= 1, в противном случае с α = 0. Зададимся некоторым и вычислим значения функции Ф в точках (1 — ) в первом случае и в точках во втором случае, где k = 1, 2,... Поиск прекращается при выполнении условия

В окрестности k-й точки производится квадратичная аппроксима­ция функции Ф(Х) и определяется из условия ее минимума (равенство нулю производной) значение , равное

где — точки, в которых известно значение аппроксими­рующей функции

Метод Матвеева предусматривает выбор оптимального парамет­ра α^(k) следующим образом:

Значение определяется, например, по следующей формуле:

i

где — i-e решаемое уравнение на k-й итерации, а второй сомножитель представляет собой максимальный по модулю элемент вектора-столбца, полученного умножением матрицы вторых производ­ных системы W(X) на вектор поправок.

Для метода Матвеева необходимо, чтобы функции w_iбыли дважды дифференцируемыми по .

Метод Матвеева требует большего по сравнению с методом Нью­тона объема вычислений и памяти, однако обладает устойчивой сходи­мостью при не очень хороших исходных приближениях. Доказано, что данный метод сколь угодно приближается к решению, даже если яко­биан стремится к нулю, т.е. матрица Якоби очень плохо обусловлена в окрестности решения.

Глава 2 Интерполяция зависимостей

2.1. Интерполяция каноническим полиномом

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

Используемые в математических моделях функции задаются как аналитическим способом, так и табличным, при котором функции из­вестны только при дискретных значениях аргументов. Ограниченный объем памяти ПЭВМ не позволяет хранить подробные таблицы функ­ций, желательно иметь возможность "сгущать"таблицы, заданные с круп­ным шагом аргумента.

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

Приближение функции f(x) более простой функцией назы­вается аппроксимацией (от латинскогоapproximo— приближаюсь). Близости этих функций добиваются путем введения в аппроксимиру­ющую функцию свободных параметров и соответ­ствующим их выбором.

В задачах электротехники широко используется аппроксимация функ­ций для физических параметров сред, для задания характеристик ак­тивных и пассивных элементов электрических и магнитных цепей и т.д. В вычислительной математике аппроксимация функций является осно­вой для разработки многих методов и алгоритмов [ 1 ].

Пусть функция f(x) задана таблицей значений, полученных из экс­перимента или путем вычислений в последовательности значений аргумента (табл. 2.1). Выбранные значения аргумента х называют узлами таблицы. Считаем, что узлы в общем случае не явля­ются равноотстоящими.

Таблица 2.1. Узлы и значения функции

x	х0		…
f			…

Введем аппроксимирующую функцию так, что­бы она совпадала с табличными значениями заданной функции f(x) во всех узлах :

(2.1)

Свободные параметры определяются из системы (2.1).

Подобный способ введения аппроксимирующей функции называ­ется лагранжевой интерполяцией, а соотношения (2.1)- условиями Лагранжа [2].

Задачей интерполяции в узком смысле считают нахождение при­ближенных значений табличной функции при аргументах х, не совпа­дающих с узловыми. Если значение аргумента х расположено между узлами , то нахождение приближенного значения функ­ции f(x) называют интерполяцией. Если интерполирующую функцию вычисляют вне интервала , то процесс называют экстраполя­цией. Происхождение этих терминов связано с латинскими словами inter— между, внутри, pole — узел, extra— вне.

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

Выберем в качестве аппроксимирующей функции полином степени пв каноническом виде:

(2.2)

Свободными параметрами интерполяции с_n являются коэффициенты полинома (2.2). Интерполяция полинома обладает такими преиму­ществами, как простота вычислений их значений, дифференцирования и интегрирования.

Коэффициенты с_nопределим из условия Лагранжа

или

(2.3)

Система линейных алгебраических уравнений (2.3) относительно свободных параметров с имеет решение, так как определитель систе­мы отличен от нуля, если среди узлов х нет совпадающих. Опреде­литель системы (2.3) называется определителем Вандермонда и имеет аналитическое выражение [2].

Рассмотренный способ вычисления интерполяционного полинома не является эффективным по затратам времени и объему памяти ЭВМ.

Независимо от формы записи полинома для заданной таблицы уз­лов и значений функции значение интерполяционного полинома явля­ется единственным. Это важное утверждение доказывается от против­ного [3].

Предположим, что для одной и той же табл. 2.1 с п + 1 узлом по­строены два полинома n-й степени Р_п(х) и Q_n(x) с разными коэффи­циентами. Запишем алгебраическое уравнение

(2.4)

левая часть которого будет также полиномом степени п. По основ­ной теореме алгебры уравнение (2.4) имеет пкорней. С другой сто­роны, в узлах значения обоих полиномов совпадают со значениями аппроксимируемой функции Значит узлы являются корнями уравнения (2.4), т.е. количество корней равно п+1. Противоречие с основной теоремой алгебры приводит к тождеству Р_п(х) = Q_n(x), что и доказывает единственность интерполяционного полинома. Единственность позволяет вводить полиномы в формах, от­личных от канонических (2.2).