Курсовая работа: Метод Ньютона и его модификации решения систем нелинейных уравнений
Название: Метод Ньютона и его модификации решения систем нелинейных уравнений Раздел: Рефераты по информатике Тип: курсовая работа | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Федеральное агентство по образованию Сочинский государственный университет туризма и курортного дела Факультет информационных технологий и математики Кафедра общей математики Курсовая работа по дисциплине «Численные методы» на тему: «Метод Ньютона и его модификации решения систем нелинейных уравнений» Выполнила: студентка 3 курса группы 06-ИНФ Лавренко М.В. Проверил: доцент, кандидат педагогических наук Иванов И.А. Сочи 2009 СОДЕРЖАНИЕ. 1. МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.4 ВЕКТОРНАЯ ЗАПИСЬ НЕЛИНЕЙНЫХ СИСТЕМ.5 1.2. ОСНОВНАЯ ТЕОРЕМА О СХОДИМОСТИ МЕТОДА НЬЮТОНА.7 2. МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.11 2.3. ТРУДНОСТИ ИСПОЛЬЗОВАНИЯ.14 3. МОДЕФИКАЦИЯ МЕТОДА НЬЮТОНА.15 3.1. УПРОЩЁННЫЙ МЕТОД НЬЮТОНА.15 3.2. ИСПОЛЬЗОВАНИЕ ФОРМУЛ ЧИСЛЕННОГО ДИФФЕРЕНЦИРОВАНИЯ.16 3.3. МЕТОД ЛОЖНОГО ПОЛОЖЕНИЯ.17 5. ЛИСТИНГ ПРОГРАММЫ НА ЯЗЫКЕ MATHCAD.. 21 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.24 В связи с развитием новой вычислительной техники инженерная практика наших дней все чаще и чаще встречается с математическими задачами, точное решение которых получить весьма сложно или невозможно. В этих случаях обычно прибегают к тем или иным приближенным вычислениям. Вот почему приближенные и численные методы математического анализа получили за последние годы широкое развитие и приобрели исключительно важное значение. В данной курсовой работе рассматривается знаменитый метод Ньютона и его модификация решения систем нелинейных уравнений. Решение систем нелинейных уравнений – одна из трудных задач вычислительной математики. Трудность состоит в том, чтобы определить: имеет ли система решение, и, если – да, то сколько. Изучается сходимость основного и упрощенного методов Ньютона и метода, получаемого из метода Ньютона применением итерационного процесса для приближенного обращения матриц Якоби. А так же коротко описываются: методы ложного положения, метод секущих, метод Стеффенсена, который чаще оказывается лучшим выбором для решения систем нелинейных уравнений нежели метод секущих или метод ложного положения. 1. МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ. Знаменитый метод Ньютона является одним из наиболее эффективных методов решения самых разных нелинейных задач. Расчётную формулу метода можно получить, используя различные подходы. Рассмотрим два из них. 1) Метод касательных. Выведем расчётную формулу метода для решения нелинейного уравнения Уравнение касательной, проведённой к графику функции
Полагая в равенстве (1.1)
Выражая из него
Благодаря такой геометрической интерпретации этот метод часто называют методом касательных . ВЕКТОРНАЯ ЗАПИСЬ НЕЛИНЕЙНЫХ СИСТЕМ. Пусть требуется решить систему уравнений
где вещественнозначные функции п
вещественных переменных
данную систему (2.1) можно записать одним уравнением
относительно векторной функции F
векторного аргумента х. Таким образом, исходную задачу можно рассматривать как задачу о нулях нелинейного отображения 2) Метод линеаризации. С наиболее общих позиций метод Ньютона можно рассматривать как итерационный метод, использующий специальную линеаризацию задачи и позволяющий свести решение исходного нелинейного уравнения к решению последовательности линейных уравнений. Пусть приближение
Здесь
Принимая решение уравнения (5) за новое приближение 1.2. ОСНОВНАЯ ТЕОРЕМА О СХОДИМОСТИ МЕТОДА НЬЮТОНА. Теорема 1. Пусть
где Следствием оценки (6) является априорная оценка:
в которой Так как Пусть
в котором
Тогда, приравняв модули обеих частей этого равенства и используя условия ограниченности
откуда следует справедливость оценки (1.6). Таким образом, при выборе начального приближения из достаточно малой окрестности корня метод Ньютона сходится квадратично. Это означает, что на каждой итерации число верных цифр приближения примерно удваивается. Приведённые в теореме 1 оценки погрешности являются априорными и их использование в практике вычислений для количественной оценки погрешности неэффективно или чаще всего невозможно. На практике предпочтительнее использование простой апостериорной оценки:
справедливость которой обосновывается следующим утверждением. Теорема 2. Пусть выполнены условия теоремы 1 и Из оценки (1.7) следует, что
из которой вытекает оценка (1.8). Наличие оценки (1.8) позволяет сформулировать следующий практический критерий окончания итерации метода Ньютона. При заданной точности
Пример 1. Используя метод Ньютона, найдём с точностью
Результаты первых итераций с 10 знаками мантиссы приведены в табл. 1. Табл. 1
При Сравнение результатов итераций со значением Пример 2. Используя метод Ньютона, укажем итерационный процесс вычисления По определению,
2. МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ. Обобщим метод Ньютона, изложенный в пункте 1 для решения одного нелинейного уравнения, на решение систем нелинейных уравнений. При этом будем исходить из трактовки метода Ньютона как метода линеаризации. Предположим, что исходя из начального приближения
каждую из функций
В результате придём к системе линейных алгебраических уравнений:
. . . . . . . . . . . . . . .
имеющей в матричной форме записи вид:
Здесь Предположим, что матрица
выражая из которого
Замечание. Формула (2.3) предполагает использование трудоёмкой операции обращения матрицы, поэтому непосредственное её использование для вычисления
относительно поправки
Сформулируем основную теорему о сходимости метода Ньютона. Теорема 3. Пусть в некоторой окрестности решения
Эта оценка означает, что метод сходится с квадратичной скоростью. Квадратичная скорость сходимости метода Ньютона позволяет использовать простой практический критерий окончания:
Пример 3. Используя метод Ньютона, найдём с точностью Возьмём
Результаты вычислений с шестью знаками мантиссы приведены в табл. 2. Табл. 2
При Трудности использования метода Ньютона не только сохраняются, но и усугубляются. Во-первых, возникает проблема вычисления на каждой итерации матрицы 3. МОДЕФИКАЦИЯ МЕТОДА НЬЮТОНА. Если оценивать качество метода Ньютона только по числу необходимых итераций, то следовало бы сделать вывод о том, что этот метод стоит применять всегда, когда он сходится. На практике для достижения разумной точности Однако при оценке общеё трудоёмкости метода следует учитывать, что на каждой итерации требуется выполнение следующей дополнительной работы: 1) вычисление 2) вычисление 3) решение системы линейных алгебраических уравнений (2.4). Существует большое число модификаций метода Ньютона, позволяющих в тех или иных ситуациях снизить его трудоёмкость либо избежать необходимости вычисления производных. Рассмотрим кратко некоторые из таких модификаций. 3.1. УПРОЩЁННЫЙ МЕТОД НЬЮТОНА. Заменим в расчётных формулах метода Ньютона (2.4), (2.5) матрицу
Этот метод сходится со скоростью геометрической прогрессии, если начальное приближение По сравнению с методом Ньютона число итераций, необходимое для достижения заданной точности 3.2. ИСПОЛЬЗОВАНИЕ ФОРМУЛ ЧИСЛЕННОГО ДИФФЕРЕНЦИРОВАНИЯ. Довольно часто вычисление производных Например, можно использовать следующую конечно-разностную аппроксимацию производной:
Параметры Если в расчётных формулах метода Ньютона (2.4), (2.5) заменить матрицу
В простейшем варианте этого метода шаги Следующие три метода можно рассматривать как варианты метода (3.3), (3.4), в которых реализованы специальные подходы к вычислению вектора Пусть Можно связать задание последовательности
где
k =1,2,3,… . Этот метод является двухшаговым и требует задания двух начальных точек К методу секущих так же, как и к методу Ньютона, можно применить пошаговую аппроксимацию обратных матриц на основе метода Шульца. Расчетные формулы этой модификации легко выписать, заменив в совокупности формул ААМН (аппроксимаиионный аналог метода Ньютона)
3.5. МЕТОД СТЕФФЕНСЕНА. Вычисления по методу Стеффенсена производят по формулам (3.3), (3.4), где Замечательно то, что хотя этот метод не требует вычисления производных и в отличие от метода секущих является одношаговым, он, как и метод Ньютона, обладает свойством квадратичной сходимости. Правда, как и в методе Ньютона, его применение затруднено необходимостью выбора хорошего начального приближения. По-видимому, для решения нелинейных систем вида Как и в одномерном случае методы секущих и Стеффенсена теряют устойчивость вблизи решения (фактически это происходит при попадании приближения Начальное приближение: Вектор-функция: Матрица Якоби вектор-функции: Вычисляем корень по формуле метода Ньютона c точностью
Ответ: 5. ЛИСТИНГ ПРОГРАММЫ НА ЯЗЫКЕ MATHCAD Вводим вектор функцию: Функция iter(x,y) вычисляет следующее приближение к корню по формуле Ньютона
Функция norma(x,y,x1,y1) вычисляет норму между текущим и следующим приближением: Функция Newton(x,y,eps) находит решение системы уравнений с точностью до eps: Найдем решение заданной системы нелинейных уравнений при начальном приближении x=0, y=-1, с точностью до 0.001: Полученное решение совпадает с рассчитанным. В данной курсовой работе был представлен метод Ньютона. Если оценивать качество метода по числу необходимых итераций, то следовало бы отметить, что этот метод стоит применять всегда, когда он сходится. Трудность использования метода Ньютона не только сохраняются при применении его к решению систем нелинейных уравнений, но и усугубляются из-за возникающей проблемы вычисления на каждой итерации матрицы Существует большое число модификаций метода Ньютона, позволяющих в тех или иных ситуациях снизить его трудоёмкость либо избежать необходимости вычисления производных. Такие модификации были также рассмотрены в данной курсовой работе: упрощённый метод Ньютона, использования формул численного дифференцирования, метод ложного положения, метод секущих, метод Стеффенсена. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ. 1. Шикин Е. В., Чхартишвили А. Г. Математические методы и модели в управлении: Учеб. пособие. – М.: Дело, 2000. – 440 с. 2. Амосов А. А., Дубинский Ю. А., Копчёнова Н. В. Вычислительные методы для инженеров: Учеб. пособие. – М.: Высш. Школа, 1994. – 544 с. 3. Демидович Б. П., Марон И. А., Шувалова Э. З. Численные методы анализа. 2-е изд., испр. и доп. – М.: Гос. изд-во физ .-мат. Лит., 1963. – 400 с. |