Методы компьютерных вычислений и их приложение к физическим задачам 2 (стр. 8 из 12)

, 1 ≤ k ≤ n. (3)

Мы получили систему линейных уравнений, неизвестными в которой выступают величины

. Решив ее, например, методом Гаусса, мы получим некое новое приближение к , т.е. . Выражение (3) можно представить как обобщение на систему уравнений итерационного метода Ньютона, рассмотренного в предыдущей главе:

, (4)

где в данном случае

– матрица Якоби, которая считается для каждого (s) приближения

Критерием окончания итерационного процесса является условие

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

Блок-схема метода Ньютона для решения систем нелинейных уравнений

Так как метод Ньютона отличается высокой скоростью сходимости при выполнении условий сходимости, на практике критерием работоспособности метода является число итераций: если оно оказывается большим (для большинства задач >100), то начальное приближение выбрано плохо.

Частным случаем решения (4) методом Ньютона системы из двух нелинейных уравнений

являются следующие легко программируемые формулы итерационного процесса:

, где ,

,

Метод простых итераций.

Метод простых итераций для решения (1) аналогичен методу, рассмотренному при решении нелинейных уравнений с одним неизвестным. Прежде всего, выбирается начальное приближение

, а исходная система уравнений преобразуется к эквивалентной системе вида

, (5)

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

Достаточным условием сходимости является

. Скорость сходимости метода сильно зависит от вида конкретно подбираемых функций , которые должны одновременно удовлетворять условиям эквивалентности (5) и (1), и обеспечивать сходимость итерационного процесса.

Например, для исходной системы уравнений

эквивалентная итерационная система (5) может быть представлена в следующем виде:

,

где множители

= –0.15и = –0.1 подбираются из анализа условий сходимости.

Метод спуска.

Рассмотрим функцию

Она неотрицательна и обращается в нуль в том и только в том случае, если

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

12. Поиск минимума функций

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

Численные методы поиска минимума функции одной переменной.

Определения.

Функция f(x) имеет локальный минимум при некотором

, если существует некоторая конечная ξ-окрестность этого элемента, в которой

,

Требуется, чтобы на множестве X функция f(x) была по крайней мере кусочно-непрерывной.

Точка, в которой функция достигает наименьшего на множестве X значения, называется абсолютным минимумом функции. Для нахождения абсолютного минимума требуется найти все локальные минимумы и выбрать наименьшее значение.

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

Методы поиска минимума по нахождению корней уравнений.

Если функция f(x) аналитически дифференцируема, то решаем f ^/(x) = 0 методами, изложенными в предыдущих главах. При этом условие f ^//(x) > 0 в найденной точке указывает нам на минимум. Для использования этих методов необходимо знать либо аналитический вид первой и второй производных, либо рассчитать их численно, если это не приведет к потере точности.

Метод дробления

Наиболее простой метод поиска минимума. Пусть дана начальная точка x₀, а также величина и знак шага h, определяющие движение из этой точки в сторону предполагаемого минимума f(x). Метод заключается в последовательном дроблении исходного шага h с изменением его знака при выполнении условия f(x_k+1) > f(x_k), где k – порядковый номер вычисляемой точки. Например, как только очередное значение функции стало больше предыдущего, выполняется h = – h/3 и процесс продолжается до тех пор, пока

|x_k+1 – x_k| ≤ ξ . (1)

Данный метод является одним из самых медленных для поиска минимума. Основное достоинство данного алгоритма – возможность использования в программах управления экспериментальными исследованиями, когда значения функции f(x) последовательно измеряются с шагом h ≥ h_min.

Метод золотого сечения.

Пусть f(x) задана и кусочно-непрерывна на [x_L, x_R], и имеет на этом отрезке только один локальный минимум. Золотое сечение, о котором упоминал ещё Евклид, состоит в разбиении интервала [x_L, x_R] точкой x₁ на две части таким образом, что отношение длины всего отрезка к его большей части равно отношению большей части к меньшей:

. (2)

Таким образом, возьмем на отрезке две точки x₁ и x₂, симметрично относительно границ делящие исходный отрезок в отношении золотого сечения:

,

,

где коэффициент

Если f(x₁) < f(x₂), мы должны сузить отрезок справа, т.е. новое значение x_R = x₂, в противном случае x_L = x₁. Оставшаяся внутри нового отрезка точка является первым приближением к минимуму и делит этот отрезок в отношении золотого сечения. Таким образом, на каждой итерации приближения к минимуму (см. рисунок) нам нужно ставить только одну точку (x₁ или x₂), в которой считать значение функции и сравнивать его с предыдущим. Условием выхода из итерационного процесса будет, подобно предыдущему случаю, условие |x₂ – x₁| ≤ ξ.

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

Метод парабол.

Пусть f(x) имеет первую и вторую производную. Разложим f(x) в ряд Тейлора в некоторой точке x_k, ограничиваясь при этом тремя членами разложения: