Цель работы: Изучение методов численного решения нелинейных уравнений — методов бисекции, хорд, простой итерации, релаксации, метода Ньютона и его модификаций; исследование скорости сходимости итерационных процедур; изучение метода Эйткена ускорения сходимости; сравнение числа итераций, необходимого для достижения заданной точности вычисления разными методами.
8.1 Краткие теоретические сведения
Численное решение нелинейного уравнения F(x)=0 заключается в вычислении с заданной точностью значения всех или некоторых корней уравнения и распадается на несколько задач: во-первых, надо исследовать количество и характер корней (вещественные или комплексные, простые или кратные), Во-вторых, определить их приближенное расположение, т. е. значения начала и конца отрезка, на котором лежит только один корень, В-третьих, выбрать интересующие нас корни и вычислить их с требуемой точностью. Вторая задача называется Отделением корней. Решив ее, по сути дела, находят приближенные значения корней с погрешностью, не превосходящей длины отрезка, содержащего корень. Отметим два простых приема отделения действительных корней уравнения — табличный и Графический. Первый прием состоит в вычислении таблицы значений функции F(x) В заданных точках Xi и использовании следующих теорем математического анализа:
1. Если функция Y=f(x) непрерывна на отрезке [а, b] и f(a)f(b) 0, то последовательные приближения сходятся к корню монотонно.
Метод релаксации — один из вариантов метода простой итерации:
.
Если функция F(x) отрицательная, то рассматривают уравнение Y= — f(x). Метод имеет линейную скорость сходимости.
Метод Ньютона (касательных). Для начала вычислений требуется задание одного начального приближения X0, последующие приближения вычисляются по формуле
.
Метод имеет квадратичную скорость сходимости для простого корня, но очень чувствителен к выбору начального приближения. При произвольном начальном приближении итерации сходятся, если всюду 
, в противном случае сходимость будет только при X0, достаточно близком к корню. Существует несколько достаточных условий сходимости. Если производные F'(X) и f»(X) Сохраняют знак в окрестности корня, рекомендуется выбирать X0 так, чтобы 
. Если, кроме этого, для отрезка [А, b], содержащего корень, выполняются условия
То метод сходится для любых X0 Î[А, b]. При вычислении кратного корня производная F'(X) близка к нулю в окрестности корня, и сходимость метода замедляется.
Модифицированный метод Ньютона применяют, если хотят избежать многократного вычисления производной:
.
Метод имеет линейную скорость сходимости.
Метод секущих Получают из метода Ньютона заменой производной F'(X), разделенной разностью, вычисленной по известным значениям Xn И Xn-1:
.
Метод является двухшаговым, его порядок сходимости a»1.618, что хуже, чем в методе Ньютона. Но в методе Ньютона на каждой итерации надо вычислять и функцию, и производную, а в методе секущих — только функцию. Поэтому при одинаковом объеме вычислений в методе секущих можно сделать больше итераций и получить более высокую точность.
Метод Эйткена ускорения сходимости. Главным является требование Линейной сходимости основного итерационного метода. В случае методов, имеющих более высокую скорость сходимости, ускорение по Эйткену неэффективно. Метод состоит в том, что после вычисления Xn, Xn+1 И Xn+2 производится пересчет по формуле
И значение yN+1 принимается за новое приближение. Оно дает лучшее приближение к корню, чем очередная итерация Xn+2. На практике не обязательно проводить пересчет на каждой итерации. Обычно он осуществляется циклически, т. е. через определенное число основных итераций.
С помощью метода Эйткена на основе известных итерационных методов получены новые, обладающие более высокой сходимостью.
Метод Вегстейна — улучшенный по Эйткену метод простой итерации; — записан в виде, позволяющем проверять целесообразность пересчета:
.
Если Rn почти постоянны, то использование в качестве очередного приближения YN+1 сильно ускорит сходимость. Итерации прекращают, если выполняется
.
Метод Стеффенсена имеет квадратичную сходимость, — более быструю, чем исходный метод релаксации:
.
8.2 Описание работы
1. Напишите программу, решающую нелинейное уравнение тремя методами (по выбору преподавателя). Предусмотрите в программе подсчет числа итераций, необходимого для достижения заданной точности e вычисления корня каждым методом.
2. Вычислите корни нечетной кратности уравнения, используя один из безусловно сходящихся методов с точностью E ( E = 10-4, 10-5, 10-6).
3. Примените метод простой итерации для нахождения одного из корней с точностью E ( E = 10-4, 10-5, 10-6) при различных начальных приближениях.
4. Вычислите все корни уравнения, используя метод Ньютона или одну из модификаций с точностью E ( E = 10-4, 10-5, 10-6) при различных начальных приближениях.
5. Примените метод Эйткена ускорения сходимости к используемым методам и исследуйте его влияние на число итераций.
8.3 Содержание отчета
1. Название и цель работы.
2. Исходная постановка задачи.
3. Результаты вычислений корней уравнения тремя методами с заданной точностью при различных начальных приближениях.
4. Результаты исследования зависимости числа итераций от требуемой точности и используемого метода.
Видео:Метод простых итераций пример решения нелинейных уравненийСкачать
Метод релаксации
В случае, изображенном на рис. 2.7, последовательные приближения смещаются все время монотонно влево и вниз. Такая картина – монотонное смещение отдельных компонент все время в одном и том же направлении – характерна для ряда классов матриц. При этом довольно часто
Рис. 2.7. Иллюстрация к методу релаксации
монотонное смещение наблюдается именно у компонент решения, скорость сходимости которых наиболее плохая. В этих случаях для ускорения сходимости прибегают к методу релаксации, который заключается в следующем. После уточнения каждой координаты по методу Зейделя производится смещение в том же направлении на р-ю часть этого смещения. Таким образом, приближения отыскиваются из соотношения
,
где D– диагональная матрица с элементами аijпо диагонали. Как показала практика вычислений, при А > 0 целесообразно брать показатель релаксации р в пределах -1 0 еще раз обратимся к геометрической картине (см. рис. 2.7). После уточнения компоненты х1 по методу релаксации при -1 Будет полезно почитать по теме:
Видео:2.2 Итерационные методы решения СЛАУ (Якоби, Зейделя, релаксации)Скачать
Курсовая работа: Метод релаксации переменных решения СЛАУ
| Название: Метод релаксации переменных решения СЛАУ Раздел: Рефераты по математике Тип: курсовая работа Добавлен 03:06:02 27 апреля 2011 Похожие работы Просмотров: 8472 Комментариев: 22 Оценило: 5 человек Средний балл: 4.4 Оценка: неизвестно Скачать | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
с помощью прямого метода — 
. Кубическая зависимость числа арифметических операций от размера матрицы СЛАУ приводит при 
к нереально большому времени решения даже на самых современных ЭВМ. Кроме того, время решения несоразмерно возрастает при использовании прямых методов в случае 
, то время решения, пропорциональное уже квадрату размера матрицы
, оказывается существенно меньше, примерно в 
раз для вещественной и 
раз для комплексной СЛАУ. Кроме того, требуется хранить в оперативной памяти, как правило, только одну матрицу, например, матрицу перехода явного итерационного метода. При использовании быстро сходящихся итерационных методов вполне решаемыми в реальном времени на современных ПЭВМ оказываются СЛАУ с комплексной матрицей размерностью 
. , | (1.1) |
А — матрица размерности 
,
Численные методы решения данной системы принято разделять на два класса: прямые методы и итерационные.
Прямыми методами называются методы, позволяющие получить решение системы уравнений (1.1) за конечное число арифметических операций.
К прямым методам относятся метод Крамера, метод Гаусса, LU — метод, метод прогонки и ряд других методов. Основным недостатком прямых методов является то, что для нахождения решения необходимо выполнить большое число операций.
Суть итерационных методов состоит в том, что решение системы (1.1) находится как предел последовательных приближений x ( n ) при n ®¥, где n — номер итерации. Применение итерационных методов требует задания начального значения неизвестных х (0) и точности вычислений e >0. Вычисления проводятся до тех пор, пока не будет выполнена оценка
 . | (1.2) |
Основное достоинство итерационных методов состоит в том, что точность искомого решения задается.
Число итераций n =n (e ), которое необходимо выполнить для получения заданной точности e , является основной оценкой качества метода. По этому числу проводится сравнение различных методов.
Главным недостатком этих методов является то, что вопрос сходимости итерационного процесса требует отдельного исследования. Доказанные в настоящее время теоремы о сходимости итерационных методов имеют место для систем, на матрицы которых наложены ограничения.
Примером обычных итерационных методов могут служить метод Якоби (метод простых итераций), метод Зейделя, метод верхних релаксаций.
К особому классу итерационных методов следует отнести вариационные итерационные методы: метод минимальных невязок, метод скорейшего спуска и т.д.
Итерационные методы также делятся на одношаговые, когда для определения решения на j +1 итерации используются значения решения, найденные на j итерации, и многошаговые, когда для определения решения на j +1 итерации используется несколько предыдущих итераций.
Заметим, что существуют системы, для которых итерационный процесс сходится, а вектор невязки, получающийся при подстановке найденного решения в исходную систему
 , | (1.4) |
получается большим по величине, т.е. найденное решение не удовлетворяет исходной системе. В этом случае в качестве критерия достижения точности решения может быть взята величина невязки, которая оценивается по одной из норм 
.
Продемонстрируем применение одношагового итерационного метода Якоби на решении системы трех уравнений. Пусть система (1.1) имеет вид
начальное приближение 
(верхний индекс указывает номер итерации), требуемая точность решения —e . Первая итерация находится из выражения
 |
 |
заменяем на 
и находим значения 
. После этого вновь проверяем, достигнута точность решения или нет. |
 |
| А=А 1 +D +A 2 , | (1.10) |
А 1 = 
— нижняя треугольная матрица,
А 2 = 
— верхняя треугольная матрица.
Представим систему (1.1) в матричной форме
 | (1.11) |
Метод Якоби в матричной записи выглядит следующим образом
 , | (1.12) |
,
.
Существуют итерационные методы, обладающие лучшей скоростью сходимости, чем методы Якоби. В этих методах при вычислении i +1 итерации 
компоненты вектора решения используются, найденные на i + 1 итерации компоненты решения с номерами 
, l =1,2. j -1. Наиболее распространенным методом подобного типа является метод Зейделя. Продемонстрируем его применение на системе (1.3). Вновь, задавая начальное приближение, для первой итерации запишем
 |
 |
 . | (1.16) |
Запишем метод Зейделя в матричной форме
 , | (1.17) |
или в форме близкой к каноническому виду
 , | (1.18) |
 . | (1.19) |
Äëÿ îäíîøàãîâûõ èòåðàöèîííûõ ìåòîäîâ, ñóùåñòâóåò êàíîíè÷åñêàÿ ôîðìà çàïèñè
 . | (1.20) |
Здесь 
— матрица, задающая тот или иной итерационный метод, 
— итерационный параметр. В случае метода Якоби — это матрица D , а =1, в случае метода Зейделя =D +А 1 , а итерационный параметр также равен единице =1.
Формируя матрицу B различным образом и задавая различные значения итерационного параметра, можно получать одношаговые итерационные методы самого разного вида. В зависимости от выбора этих параметров мы будем получать методы, которые будут обладать различной скоростью сходимости, т.е. заданная точность будет достигаться за разное число итераций.
Одним из наиболее распространенных одношаговых итерационных методов является метод верхних релаксаций * , который имеет следующий вид
 , | (1.21) |
где w >0 — заданный числовой параметр. Этот параметр выбирается таким образом, чтобы на каждом шаге итерационного процесса уменьшалась величина, характеризующая близость полученного решения к искомому решению системы.
Для получения расчетных формул (1.21) перепишем в виде
 , | (1.22) |
или в покомпонентной записи получим
 . | (1.23) |
Приведем несколько строк покомпонентной записи
 , | (1.24) |
 , | (1.25) |
 | (1.26) |
Практика применения итерационных методов показала, что эти методы приводят к правильному решению для систем с матрицей А имеющей специальный вид. Приведем ряд теорем о сходимости итерационных методов. Доказательства этих теорем приводятся в книге [1].
Рассмотрим итерационные методы с постоянным итерационным параметром, записанные в виде
 . | (1.27) |
Пусть А — симметричная положительно определенная матрица, t >0 и пусть выполнено неравенство В- 0,5t А >0. Тогда итерационный метод (1.27) сходится.
Пусть А — симметричная положительно определенная матрица с диагональным преобладанием, т.е.
 | (1.28) |
Тогда метод Якоби сходится.
Пусть А — симметричная положительно определенная матрица. Тогда метод верхних релаксаций сходится при условии 0 g 2 . При 
итерационный метод (1.27) сходится и для погрешности справедливы оценки
 , i =0,1. | (1.29) |
 | (1.30) |
 , | (1.31) |
 , | (1.32) |
 . | (1.33) |
Если А Т =А >0, то для метода простой итерации
 | (1.34) |
 | (1.35) |
 , | (1.36) |
 | (1.37) |
 | (1.38) |
Для симметричной матрицы А и
 | (1.39) |
 , | (1.40) |
где ,. В приложениях часто встречаются задачи с плохо обусловленной матрицей А , когда отношение 
велико. В этом случае число r 0 близко к единице, и метод простой итерации сходится медленно.
Оценим число итераций n 0 (e ), которое требуется для достижения заданной точности e в случае малых x , т.е. для получения оценки
 . | (1.41) |
Из условия 
получаем, что
 , | (1.42) |
и при малых x имеем
 . | (1.43) |
Заметим, что в качестве критерия сходимости итерационного метода может использоваться невязка, которая получается при подстановке найденного решения в систему (1.1).
1.1 Метод верхних релаксаций
линейный уравнение итерационный релаксация
Среди явных одношаговых итерационных методов наибольшее распространение получил метод верхних релаксаций (1.21). Это связано с тем, что метод верхних релаксаций содержит свободный параметрw , изменяя который можно получать различную скорость сходимости итерационного процесса.
Наиболее эффективно этот метод применяется при решении множества близких алгебраических систем линейных уравнений. На первом этапе проводится решение одной из систем с различными значениями итерационного параметраw и из анализа скорости сходимости итерационного процесса выбирается оптимальное значение этого параметра. Затем все остальные системы решаются с выбранным значением w .
Еще одно достоинство итерационного метода верхних релаксаций состоит в том, что при его реализации на ЭВМ алгоритм вычислений имеет простой вид и позволяет использовать всего один массив для неизвестного вектора.
Основная вычислительная формула имеет вид
| (1.44) |
В выражение (1.44) 
и 
входят одинаковым образом, следовательно, при вычислениях они могут записываться в один и тот же массив. При реализации метода верхних релаксаций используется следующая форма записи алгоритма вычислений
 . | (1.45) |
Действительно, при последовательном нахождении элемента 
(i +1 итерации) на каждом шаге будут использоваться найденные ранее значения, которые при k j — i итерации.
Современная вычислительная техника позволяет проводить исследование устойчивости и сходимости итерационного метода в зависимости от параметров задачи. Например, можно проводить исследование влияния повышения точности решения задачи на число необходимых итераций, исследование влияния начального приближения, изменения коэффициентов матрицы А и правых частей системы.
1.2 Âû÷èñëèòåëüíûå ïîãðåøíîñòè ìåòîäà âåðõíèõ ðåëàêñàöèé
Один из основных вопросов применения итерационных методов связан с корректностью выбора точности метода e.
Àíàëèçèðóÿ âû÷èñëèòåëüíûå ïîãðåøíîñòè âûðàæåíèÿ (1.45), ïîëó÷èì îöåíêó íàèìåíüøåãî çíà÷åíèÿ òî÷íîñòè ìåòîäà âåðõíèõ ðåëàêñàöèé.
Очевидно, что искомая погрешность вычислений будет определяться погрешностью задания коэффициентов исходной системы и погрешностью округления.
Çàïèøåì ðàçíîñòü äâóõ èòåðàöèîííûõ ïðèáëèæåíèé ðåøåíèÿ è îöåíèì å¸ ìèíèìàëüíîå çíà÷åíèå
 | (1.46) |
Пусть коэффициенты 
и fi заданы с некоторой относительной погрешностью 
. Предположим, что итерационный метод сходится, и невязка
 | (1.47) |
бывает с ростом номера итерации k , т.е. 
. Оценка абсолютной погрешности правой части выражения (10) может быть представлена в следующем виде
 , | (1.48) |
здесь 
.- модуль минимального значения диагонального элемента 
.Отсюда следует, что задаваемая погрешность метода 
.
1.3 Ìåòîä áëî÷íîé ðåëàêñàöèè
Èñõîäíàÿ ìàòðèöà 
ðàçáèâàåòñÿ íà áëîêè (â ðàìêàõ ëàáîðàòîðíîé ðàáîòû áóäåì ðàññìàòðèâàòü ñëó÷àé, êîãäà ðàçáèâàåòñÿ íà êâàäðàòíûå áëîêè ðàâíîé ðàçìåðíîñòè). Âåêòîð ïðàâîé ÷àñòè è âåêòîð íåèçâåñòíûõ ðàçáèâàþòñÿ íà áëîê-âåêòîðû ñîîòâåòñòâóþùåé ðàçìåðíîñòè. Íàïðèìåð, äëÿ ðàçìåðà áëîêà ðàâíîãî äâóì, ïîëó÷àåì:
 |
 | (1.50) |
 | (1.51) |
  | (1.52) |
Çàïèøåì ôîðìóëó äëÿ áëîêîâ ìàòðèöû è áëîê-âåêòîðîâ 
è 
:
 | (1.53) |
 | (1.54) |
 | (1.55) |
Òîãäà, ïîäñòàâëÿÿ (1.54) è (1.55) â (1.53) è óìíîæàÿ ñëåâà íà 
, äëÿ êàæäîãî áëîê-âåêòîðà 
ïîëó÷àåì ÑËÀÓ:
 | (1.56) |
Ðåøåíèå ïîëó÷åííûõ ñèñòåì (1.56) ðåêîìåíäóåòñÿ âûïîëíÿòü ñ èñïîëüçîâàíèåì ôàêòîðèçàöèè ìàòðèöû , ïðè÷¸ì ôàêòîðèçàöèþ ñëåäóåò âûïîëíÿòü 1 ðàç ïåðåä ïåðâîé èòåðàöèåé.
2. ÐÀÇÁÎÐ ÌÅÒÎÄÀ ÐÅËÀÊÑÀÖÈÉ Â ÑÈÑÒÅÌÀÕ ËÈÍÅÉÍÛÕ ÓÐÀÂÍÅÍÈÉ ÍÀ ÏÐÈÌÅÐÅ
ПРИМЕР: решить методом релаксаций данную систему
 |
 |
 | (2.3) |
Находим значения невязок
 |  |  |  |  |  |
| 0 | 0,60 | 0 | 0,70 | 0 | 0,80 |
| 0,16 | 0,16 | -0,80 | |||
| 0,76 | 0,86 | 0 | |||
| 0,17 | 0,86 | -0,86 | 0,09 | ||
| 0,93 | 0 | 0,09 | |||
| 0,93 | -0,93 | 0,09 | 0,09 | ||
| 0 | 0,09 | 0,18 | 0,18 | ||
| 0,04 | 0,04 | -0,18 | |||
| 0,04 | 0,13 | 0,13 | 0 | ||
| 0,03 | -0,13 | 0,01 | |||
| 0,07 | 0,07 | 0 | 0,01 | ||
| -0,07 | 0,01 | 0,01 | |||
| 0 | 0,01 | 0,02 | 0,02 | ||
| 0 | 0 | -0,02 | |||
| 0 | |||||
| 0 | 0,01 | 0,01 | 0 | ||
| 0 | -0,01 | 0 | |||
| 0 | 0 | 0 | |||
 | 1,00 | 1,00 | 1,00 |
И так далее. Подставляем результаты вычисленные в таблице. Подсчитав все приращения 
, содержащее значение корней 
Для проверки подставляем найденные значения корней в исходное уравнение; в целом система решена точно.
Рисунок 1 – Решение системы с помощью языка Borland C++
Листинг программы решающий систему методом релаксаций переменных приведен в приложении.
Можно утверждать, что почти любая задача вычислительной математики сводится в конечном итоге к решению полученной некоторым образом системы линейных или тензорных алгебраических уравнений (СЛАУ).
Но такие системы уравнений могут быть, во-первых, очень большого размера, например, NxN=10000х10000, и даже более; во-вторых, система уравнений может оказаться недоопределенной; в-третьих, она может оказаться с линейно зависимыми уравнениями; в-четвертых, она может оказаться переопределённой и несовместной. Кроме того, в-пятых, вычислительная техника может иметь далеко не рекордное быстродействие и объём оперативной памяти, и заведомо конечную разрядность двоичного представления чисел и связанные с этим ненулевые вычислительные погрешности. Поэтому итерационные методы получили большое применение в решении СЛАУ. Современная вычислительная техника позволяет проводить исследование устойчивости и сходимости итерационного метода в зависимости от параметров задачи.
Наиболее эффективно метод релаксаций применяется при решении множества близких алгебраических систем линейных уравнений. На первом этапе проводится решение одной из систем с различными значениями итерационного параметраw и из анализа скорости сходимости итерационного процесса выбирается оптимальное значение этого параметра. Затем все остальные системы решаются с выбранным значением w .
Еще одно достоинство итерационного метода верхних релаксаций состоит в том, что при его реализации на ЭВМ алгоритм вычислений имеет простой вид и позволяет использовать всего один массив для неизвестного вектора.
Я научился решать систем линейных уравнений методом релаксации(ослабления) переменных, и закрепил приобретённые навыки разработкой программы на языке Borland C++ 4.5.
1. Воеводин В.В. «Вычислительные основы линейной алгебры». Москва «Наука», 1977.
2. Фаддеев Д.К., Фаддеева В.Н. «Вычислительные методы линейной алгебры». Москва «Физматгиз», 1963.
3. Самарский А.А., Гулин А.В.» Численные методы». Москва «Наука», 1989.
4. Самарский А.А., Николаев Е.С. «Методы решения сеточных уравнений». Москва «Наука», 1978.
5. Самарский А.А. «Введение в численные методы». Москва «Наука», 1987.
6. Стренг Г. «Линейная алгебра и ее применение». Москва «Мир», 1980.
7. Карманов В.Г. «Математическое программирование». Москва «Наука», 1989.
8. Алексеев Е.Р. «Программирование на С++». Москва «НТ Пресс», 2007.
9. http://www.exponenta.ru/ — сайт посвящен решению математических задач в прикладных программных пакетах.
10. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. — М.: Наука, 1987.- 600 с.
📽️ Видео
Метод простой итерации Пример РешенияСкачать
Метод половинного деления решение нелинейного уравненияСкачать
1 3 Решение нелинейных уравнений методом простых итерацийСкачать
10 Численные методы решения нелинейных уравненийСкачать
Метод Зейделя Пример РешенияСкачать
Метод Ньютона (метод касательных) Пример РешенияСкачать
После этого видео, ТЫ РЕШИШЬ ЛЮБУЮ Систему Нелинейных УравненийСкачать
Методы решения систем нелинейных уравнений. Метод Ньютона. Численные методы. Лекция 14Скачать
МЗЭ 2021 Лекция 11 Метод Ньютона для решения систем нелинейных уравненийСкачать
Решение нелинейного уравнения методом простых итераций (программа)Скачать
Вычислительные методы алгебры - Метод релаксации, градиентного спуска, минимальных невязокСкачать
Методы численного анализа - Метод Ньютона, секущих для решения систем нелинейных уравненийСкачать
Метод итерацийСкачать
Способы решения систем нелинейных уравнений. 9 класс.Скачать
15 Метод Ньютона (Метод касательных) Ручной счет Численные методы решения нелинейного уравненияСкачать
4.2 Решение систем нелинейных уравнений. МетодыСкачать
Способы решения систем нелинейных уравнений. Практическая часть. 9 класс.Скачать
Численные методы. Лекция 2. Матричные задачи. Решение нелинейных уравненийСкачать
