Критерии усвоения

Содержание темы

Входная информация для самопроверки

ММ-5. Ключевые слова и понятия

ММ-5. МЕТОД НЬЮТОНА. МОДИФИЦИРОВАННЫЙ МЕТОД НЬЮТОНА. МЕТОД СЕКУЩИХ

5.1. Метод Ньютона для решения одного нелинейного уравнения

5.2. Метод Ньютона для решения системы нелинейных уравнений

5.3. Модифицированнный метод Ньютона для решения нелинейного уравнения или системы нелинейных уравнений

5.4. Метод секущих решения нелинейного уравнения или системы нелинейных уравнений

Для изучения данной темы Вам необходимо восстановить в памяти:

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

- из настоящего спецкурса - понятия: пространства, оператора, функционала, линейного оператора.

5.2.1. Структурно – логическая схема содержания темы

5.2.2. Тематическое содержание

Для решения нелинейного операторного уравнения методом простых итераций это уравнение должно иметь определённый вид. Более широкие возможности предоставляет метод Ньютона, или метод касательных, а также некоторые родственные ему методы (модифицированный, или упрощенный, метод Ньютона, усиленный метод Ньютона, метод секущих).

В операторном представлении уравнения, которые решаются этим методом, выглядят так

, (5.1)

где - оператор, в общем случае, нелинейный; - нормированное пространство; ; - нулевой элемент этого пространства.

Для нас требование, чтобы оператор действовал из нормированного пространства в нормированное пространство, не является обременительным, так как состояние рассчитываемых объектов описывается только скалярами, векторами или функциями, а соответствующие пространства (), как мы видели, - нормированные.

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

в случае одного нелинейного уравнения -

, (5.2)

в случае системы нелинейных уравнений -

(5.3)

где - числовые функции действительных аргументов (одного аргумента или нескольких аргументов ).

Система (5.3) может быть записана более компактно в векторных обозначениях

, (5.3а)

где - -мерная вектор-функция аргументов; мерный нуль-вектор.

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

Применение метода Ньютона предполагает выполнение некоторых условий, налагаемых на функции в левой части уравнений (5.2) и (5.3), а также на область, в которой предполагается осуществлять поиск корня (корней) этих уравнений. Совокупность этих условий достаточна для реализуемости метода. В любом случае выделяется подобласть, в которой находится только одно решение (один корень в случае одного уравнения и один вектор в случае системы уравнений). Этому соответствует одна перемена знака функции (функций) в пределах указанной подобласти. Указанные функции должны быть непрерывными вместе со своими первыми и вторыми производными (; - подобласти поиска), причём эти производные должны сохранять знак в пределах той же подобласти. Очень важное, но трудно контролируемое, условие - начальное приближение (см. лекцию ММ-4) должно быть достаточно близко к точному решению (которое, естественно, неизвестно).

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

; (5.4)

(5.5)

(5.6)

(5.7)

(5.8)

(5.9)

; (5.10)

В (5.9) -корень уравнения (5.2), -достаточно малая величина.

Условие (5.4) гарантирует наличие первой производной, которая используется в процессе вычислений, а также наличие непрерывной второй производной, что необходимо (но не достаточно) для обеспечения сходимости последовательности решений. Условия (5.5) и (5.6) обеспечивают единственность корня на заданной области. Выполнение условий (5.7) и (5.8) достаточно для обеспечения сходимости (при выполнении остальных условий). Неравенства (5.9) и (5.10) задают условия для выбора начальной точки.

Схема метода Ньютона для решения одного нелинейного уравнения (5.2) соответствует общей идее итерационных методов, описанной в лекции ММ-4, и выглядит следующим образом.

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

Это наименее формализованная, основанныая на интуиции часть расчёта. Она заключается в том, что по виду уравнения проверяется его соответствие требованию (5.4) и определяются (возможно, достаточно грубо) приближённые значения всех корней, после чего вся заданная область поиска корней разбивается на подобласти, в каждой из которых находится один и только один корень. Поведение функции уравнения (5.2) в пределах каждой подобласти должно удовлетворять условиям (5.5)-(5.8). При этом каждая подобласть будет принадлежать области сходимости лежащего в ней корня.

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

Второй этап. Выполняется требуемое число раз определение приближённого решения (с использования полученного на предыдущем приближении решения) и сравнение оценки погрешности очередного приближённого решения с допустимой величиной погрешности (см. лекцию ММ-1).

По результатам этого сравнения принимается решение о продолжении процесса или о выходе из итерационного цикла.

В методе Ньютона поиск приближённого решения выполняется следующим образом.

На каждой - той итерации () функция аппроксимируется линейной функцией

. (5.11)

Очевидно, что для первого приближения . Если функция , можно считать, что аппроксимируется конечным (двучленным) отрезком ряда Тейлора.

Угловой коэффициент аппроксимации принимается из условия, что график аппроксимации совпадает с касательной к графику функции в точке, совпадающей предыдущим корнем, то-есть, . Это соответствует коэффициенту при первой степени приращения аргумента в ряде Тейлора (когда ). На этом основании метод Ньютона называют также методом касательных (рис. 5.1).

Рис. 5.1.

В качестве приближённого значения искомого корня на - ой итерации принимается корень аппроксимации на этой итерации:

. (5.12)

откуда

. (5.13)

Условие (5.8) как раз и обеспечивает возможность выполнения вычислений по формуле (5.13).

Как следует из (5.13), алгоритм метода Ньютона для уравнения (5.2) соответствует алгоритму метода простых итераций для уравнения

, (5.14)

где

. (5.15)

Как было определено в лекции ММ-4, условие сходимости метода простых итера- ций для уравнения (5.15) имеет вид

, (5.16)

что и даёт второе условие (5.7).

Известны оценки погрешности очередного - го приближения

, (5.17)

, (5.18)

, (5.18)

где

, (5.19)

, (5.20)

, (5.21)

- точное (неизвестное) значение корня уравнения (5.2).

5.1. Метод Ньютона для решения одного нелинейного уравнения (Адрес файла Блок____4)   Методом Ньютона для одного уравнения вида называется следующая последовательность вычислительных процедур. 1. Проверка возможности использования метода и разделение корней. 2. Выбор начальных точек каждой подобласти. 3. Последовательное выполнение (для каждой подобласти) итераций, причём любая - ая итерация выполняется по формуле . 4. Условием выхода из цикла является выполнение неравенства , где - оценка погрешности;- допускаемая погрешность. Вернитесь к тексту    

Последовательное выполнение (для каждойподобласти)

Перейдём к решению системы нелинейных уравнений (5.3).

Подготовительный этап также плохо формализован. Проверяется условие

, (5.22)

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

Первый этап аналогичен случаю одного уравнения – выбираем начальное приближение в каждой подобласти.

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

, (5.23)

где - матрица Якоби системы функций

=. (5.24)

Функция - полилинейная относительно .

Решая линейную алгебраическую систему уравнений (5.23) относительно вектора , получим приближённое выражение для выполнения - ой итерации

. (5.25)

Из (5.25) видно, что, по аналогии с требованием в случае одного уравнения, для применения метода Ньютона при решении системы уравнений необходимо выполнение условия

, (5.26)

то – есть, матрица, обратная к матрице Якоби, должна быть неособенной на всей области поиска решения.

Итак, для применения метода Ньютона при решении системы уравнений будем требовать выполнения условий (5.22) и (5.26). а также достаточной близости начальной точки неизвестному (но каким-то образом приближённо оцениваемому) точному решению.

5.1. Метод Ньютона для одного нелинейного уравнения

(Адрес файла Блок____4)

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

, (5.13а)

. (5.25а)

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

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

Известен также усиленный метод Ньютона, когда аппроксимирующее выражение принимают в виде полинома порядка более высокого, чем первый. При бесконечной дифференцируемости функций его можно рассматривать как более длинный, чем в обычном методе Ньютона, отрезок ряда Тейлора. Однако, более высокие затраты времени на выполнение одной итерации в ряде случаев могут сильнее сказаться на времени счёта, чем уменьшение требуемого количества итераций.

При выполнении реальных расчётов строительных конструкций определение производных функций, стоящих в левой части уравнений (5.2) или (5.3), может оказаться затруднительным или вовсе невозможным (например, из-за того, что определение усилий в железобетонных конструкциях описывается достаточно сложным алгоритмом, включающим условные операторы); возможно только определение самих усилий, а не их дифференцирование по перемещениям или даже по деформациям.

В этом случае может быть применён конечноразностный вариант метода Ньютона или модифицированного метода Ньютона, а именно, использование в формулах (5.13), (5.13а), (5.25) и (5.25а) вместо производных их конечноразностных аппроксимаций (возможно, но не всегда целесообразно применение конечноразностных аналогов производных более высоких порядков). Приращения функций и аргументов естественно определять по их значениям при последовательных итерациях (частные приращения функций определяются при изменении только одного аргумента, номер которого является вторым нижним индексом функции):

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

Следует отметить, что решение уравнения (5.23) в виде (5.25) имеет скорее символический, чем практический смысл, так как обращение матрицы в общем случае гораздо более трудоёмко, чем непосредственное решение системы уравнений. Целесообразнее решать сразу систему (5.23) (или соответствующую ей систему модифицированного метода).

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

После изучения содержания данной темы Вы должны:

·

знать

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

каким условиям должны удовлетворять уравнения для того, чтобы их можно было решать методом Ньютона;

как контролируется погрешность очередной итерации;

когда следует отказаться то применения метода Ньютона и переходить к методу секущих;

· понимать

роль каждого условия применения метода Ньютона;

смысл алгоритма решения на каждой итерации;

причину и смысл перехода к модифицированному методу Ньютона;

причину отказа от применения метода Ньютона и перехода к методу секущих;

· Уметь

Применять каждый из ииизложенных методов.

Дата добавления: 2014-01-20