Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Численные методы решения нелинейных уравнений, используемые в прикладных задачах. Нахождение корня уравнения методом простой итерации и методом хорд

Численные методы решения нелинейных уравнений, используемые в прикладных задачах. Нахождение корня уравнения методом простой итерации и методом хорд

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	15.06.2013
Размер файла	849,1 K

посмотреть текст работы

скачать работу можно здесь

полная информация о работе

весь список подобных работ

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

ФГОУ СПО «Уфимский авиационный техникум»

Курсовая работа

Численные методы решения нелинейных уравнений, используемые в прикладных задачах. Нахождение корня уравнения методом простой итерации и методом хорд

по дисциплине «Численные методы»

КР 080802.10.038.03 ПЗ

Студент А.Б. Бобронников

Руководитель работы Э.Р. Ахматсафина

Содержание

Введение

1. Теоретическая часть

1.1 Метод простой итерации

1.2 Метод хорд

2. Постановка и решение задачи

2.1. Формулировка задачи

2.2 Решение методом простых итераций

2.3 Решение методом хорд

3. Программная реализация

3.1 Метод итераций

3.1.1. Блок схема

3.1.2 Программа

3.1.3 Тестовый пример

3.1.4 Решение задачи с помощью ЭВМ

3.2 Метод хорд

3.2.1 Блок схема

3.2.2 Программа

3.2.3 Тестовый пример

3.2.4 Решение задачи с помощью ЭВМ

Заключение

Список используемой литературы

Введение

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

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

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

Цель: рассмотреть два метода нахождения приближенного корня уравнения и применить их на практике:

- метод хорд

- метод простой итерации.

Состав курсовой работы:

Первая часть - Теоретическая:

В ней описывается теоретическая часть обоих методов.

Вторая часть - Практическая:

В ней реализована практическая реализация обоих методов.

Третья часть - Программная:

В ней реализованы методы с помощью программного языка ЭВМ.

1. Теоретическая часть

1.1 Метод простой итерации

Предположим, что уравнение при помощи некоторых тождественных преобразований приведено к виду.

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

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

по формулам

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

Заметим: тот факт, что - корень уравнения , означает, что есть абсцисса точки пересечения графика с прямой y=x. Если же при каком-либо вычислено значение и взято в качестве нового аргумента функции, то это означает, что через точку графика проводится горизонталь до прямой y=x, а оттуда опускается перпендикуляр на ось . Там и будет находиться новый аргумент .

Рисунок 1. Точка - решение уравнения . Построение точки x1 по точке x0

Проследим, как изменяются последовательные приближения xi при различных вариантах взаимного расположения графика и прямой y=x.

1). График расположен, по крайней мере в некоторой окрестности корня, включающей начальное приближение x0, в некотором угле со сторонами, имеющими наклон менее к горизонтали (то есть стороны угла - прямые

где ):

Рисунок 2. График пересекает прямую y=x под малым углом: варианты расположения

Если предположить вдобавок, что функция имеет производную , то этот случай соответствует тому, что выполнено неравенство , при , близких к корню . Проследим в этом случае за поведением последовательных приближений

Рисунок 3. Сходящиеся к корню приближения в случае : два варианта

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

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

хорда итерация приближение уравнение

Рисунок 4. В случае немонотонной функции сходящиеся итерации могут вести себя нерегулярно

2). График расположен, по крайней мере в некоторой окрестности корня, вне некоторого угла со сторонами, имеющими наклон более к горизонтали (то есть стороны угла - прямые , где )

Рисунок 5. График пересекает прямую под большим углом: варианты расположения

Если функция имеет производную , то в этом случае при , близких к корню , выполнено неравенство .

Рисунок 6. Числа расходятся в случае : два варианта

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

Ещё одно замечание: если не выполнено ни условие , ни условие , то итерации могут зацикливаться. На чертеже ниже приведён пример зацикливания, когда уравнение имеет вид .

Рисунок 7. Пример зацикливания итераций

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

Теорема Если функция имеет производную в некоторой окрестности корня уравнения , причём при , то последовательность итераций , полученных при , начиная с , сходится к корню .

При этом скорость сходимости задаётся неравенствами

где -- длина окрестности , а точность -го приближения -- оценкой

Доказательство. Пусть . По формуле конечных приращений, применённой к отрезку между точками и , получаем

где лежит между и . Значит, то есть (напомним, что и ). Повторяя рассуждения для точек вместо , получаем

Так как , последовательность стремится к 0 при . Значит, при .

Неравенство очевидно, поскольку из того, что и лежат в окрестности длины , следует, что .

Поскольку

мы имеем

так как и

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

Рисунок 8. Быстрая сходимость итераций при горизонтальной касательной к графику

Выше мы отмечали, что привести уравнение к виду можно, выбирая в виде

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

1.2 Метод хорд

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

В зависимости от того, лежат ли точки и по разные стороны от корня или же по одну и ту же сторону, получаем такие чертежи

Рисунок 9. Построение последовательного приближения по методу хорд: два случая

Итак, очередное последовательное приближение будет зависеть от двух предыдущих: . Найдём выражение для функции .

Интерполяционную линейную функцию будем искать как функцию с угловым коэффициентом, равным разностному отношению

построенному для отрезка между и , график которой проходит через точку

Решая уравнение , находим

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

Вычисление по формуле (1) гораздо предпочтительнее вычисления по другой полученной нами формуле

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

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

2. Постановка и решение задачи

2.1 Формулировка задачи