Численные методы линейной и нелинейной алгебры

Стр 1 из 6Следующая ⇒

Численные методы линейной и нелинейной алгебры

Методическое руководство к практическим работам по методам вычислений для студентов естественных наук

Саратов-2011

Содержание

Глава 1. Численные методы решения нелинейных уравнений с одним неизвестным. 3

1. Метод деления отрезка пополам (метод бисекций). 4

2. Метод хорд (метод секущих). 5

3. Метод Ньютона (метод касательных). 6

4. Модифицированный метод Ньютона. 6

5. Метод простой итерации. 7

Задания. 12

Глава 2. Численные методы решения систем нелинейных уравнений. 13

1.Метод простой итерации. 13

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

Задания. 22

Глава 3. Численные методы решения систем линейных алгебраических уравнений (СЛАУ). 23

1. Метод итерации. 23

2. Метод простой итерации. 26

3. Стационарный метод Зейделя. 28

4. Нестационарный метод Зейделя. 30

5. Метод Некрасова. 31

Задания. 32

Литература. 35

Глава 1. Численные методы решения нелинейных уравнений с одним неизвестным.

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

Предварительные замечания. В вычислительной практике часто приходится находить корни нелинейных уравнений вида:

, (I)

где некоторая непрерывная функция.

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

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

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

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

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

Метод хорд (метод секущих).

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

Сначала запишем уравнение хорды , как прямой, проходящей через две точки и .

Тогда значение , соответствующее точке пересечения хорды с осью Ох, будет

(2.1)

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

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

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

При использовании этого метода исходное нелинейное уравнение (I) записывается в виде

(5.1)

Пусть начальное приближение к корню уравнения (6.1) известно и равно

(5.2)

Подставим (5.2) в правую часть (5.1) и получим

(5.3)

Подставляя (5.3) в правую часть (5.1), получаем

(5.4)

и т.д.

Таким образом, рабочая формула метода простой итерации имеет вид

, (5.5)

Счет по формуле (5.5) проводить до тех пор, пока не будет выполняться условие

, или (5.6)

Достаточным условием сходимости метода простой итерации является условие .

Блок-схема метода простой итерации может быть следующей.

Блок-схема (метод простой итерации)

Блок-схема (метод бисекций)

Блок-схема (метод секущих)

Блок-схема (метод касательных)

Задания.

Во всех заданиях уточнить действительные корни уравнений с заданной точностью указанным методом.

10.

11.

12.

13.

14.

15.

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

Запишем систему нелинейных уравнений в виде

(1.1)

или коротко в виде , где .

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

(1.2)

Для того, чтобы систему (1.1) решить методом простой итерации, во-первых, преобразуем её к виду

(1.3)

или, коротко к виду, , где .

Функции, стоящие справа в (1.3) обладают теми же свойствами, что и функции в (1.1).

Во-вторых, в области D выберем любую точку и назовём её нулевым приближением к точному решению системы (1.3).

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

Будем иметь

1.4)

или коротко

Величины , стоящие слева в формулах (1.4), будем считать координатами точки . Эту точку назовём первым приближением к точному решению исходной системы, т.е. к . Теперь мы имеем два приближённых решения системы (1.3). Этими решениями являются и .

В четвёртых, сравним эти два приближённых решения на :

(1.5)

или коротко

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

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

(1.6)

или коротко

Далее надо сравнить приближения и на по формуле (1.5). Строить приближения надо до тех пор, пока два соседних приближения и будут отличаться друг от друга не больше чем на .

Запишем рабочие формулы метода простой итерации для системы (1.3) в компактном виде.

Вычислить

(1.7)

и построить приближения к решению системы (1.3)

для всех и (1.8)

Сформулируем алгоритм вычислений по формулам (1.7) и (1.8).

1. Выберем , принадлежащую D.

2. В (1.7) положим , получим

3. По (1.8) построим .

4. Проверим условие (1.5) на :

5. Если все условия в п.4 выполнены, то заканчиваем вычисления, выбрав за приближённое решение исходной системы или всё равно, т.к. эти решения отличаются друг от друга не больше чем на . Если хотя бы одно из условий в п.4 не выполнилось, то переходим к п.6.

6. В (1.7) положим и получим

7. По (1.8) построим .

8. Перейдём к п.4, при этом верхние индексы в условии (1.5) изменятся и станут на единицу больше.

Запишем этот алгоритм геометрически.

Задания

Во всех заданиях требуется:

1. Составить программу численной реализации метода, согласно предложенному алгоритму.

2. Получить результаты вычислений.

3. Проверить полученные результаты.

Задана система двух нелинейных уравнений.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. .

Метод итерации.

Пусть СЛАУ задана в виде

(1.1)

Эту систему можно записать в матричном виде

, (1.2)

где - матрица коэффициентов при неизвестных в системе (1.1), - столбец свободных членов, - столбец неизвестных системы (1.1).

Будем считать, что система (1.1) определена и совместна, т.е. имеет единственное решение. Это решение обозначим

. (1.3)

Решим систему (1.1) методом итерации. Для этого выполним следующие действия.

Во-первых. Выберем нулевое приближение

(1.4)

к точному решению (1.3) системы (1.1). Компонентами нулевого приближения могут быть любые числа. Но удобнее за компоненты нулевого приближения взять либо нули , либо свободные члены системы (1.1)

Во-вторых. Компоненты нулевого приближения подставим в правую часть системы (1.1) и вычислим

(1.5)

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

В-третьих. Проверим нулевое и первое приближения на

(1.6)

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

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

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

Итерации нужно строить до тех пор, пока два соседних приближения и будут отличаться друг от друга не больше, чем на .

Рабочую формулу метода итерации решения системы (1.1) можно записать в виде

(1.7)

Алгоритм численной реализации формулы (1.7) может быть таким.

1. Выберем , где , если не оговорено особо.

2. Положим .

3. Вычислим для всех

4. Проверим условия , .

5. Если все условия в п.4 будут выполнены, то за приближённое решение системы (1.1) выберем либо , либо и закончим вычисления. Если хотя бы одно условие в п.4 не будет выполнено, перейдём к п.6.

6. Положим и перейдём к п.3.

Этот алгоритм можно записать геометрически.

Достаточные условия сходимости метода итерации для системы (1.1) имеют вид

1. , .

2. , .

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

Пусть система линейных алгебраических уравнений (СЛАУ) задана в виде

(2.1)

Чтобы систему (2.1) решить методом простой итерации, её сначала надо привести к виду

(2.2)

В системе (2.2) -ое уравнение представляет собой -ое уравнение системы (2.1), разрешённое относительно –ой неизвестной ( ).

Метод решения системы (2.1), состоящий в сведении её к системе (2.2) с последующим решением системы (2.2) методом итерации, называется методом простой итерации для системы (2.1).

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

(2.3)

Формулы (2.3) можно записать в виде

(2.4)

Алгоритм численной реализации метода простой итерации для системы (2.1) по формулам (2.4) может быть таким.

1. Выберем , если не оговорено особо.

2. Положим .

3. Для всех вычислим

4. Проверим условия , .

5. Если все условия в п.4 будут выполнены, то за приближённое решение системы (2.1) выберем, либо , либо и закончим вычисления. Если хотя бы одно условие в п.4 не будет выполнено, перейдём к п.6.

6. Положим и перейдём к п.3.

Этот алгоритм можно записать геометрически.

Достаточные условия сходимости метода простой итерации для системы (2.1) имеют вид

1. , .

2. , .

Стационарный метод Зейделя.

Метод Зейделя решения СЛАУ отличается от метода итерации тем, что найдя какое-то приближение для -той компоненты, мы сразу же используем его для отыскания следующих , , …, -ой компонент. Такой подход позволяет обеспечить более высокую скорость сходимости метода Зейделя по сравнению с методом итерации.

Пусть СЛАУ задана в виде

(3.1)

Пусть - нулевое приближение к точному решению системы (3.1). И пусть найдено -ое приближение . Определим компоненты -ого приближения по формулам

(3.2)

Формулы (3.2) можно записать в компактном виде

, , (3.3)

Алгоритм численной реализации метода Зейделя решения системы (3.1) по формулам (3.3) может быть таким.

1. Выберем , например, ,

2. Положим .

3. Для всех вычислим .

4. Для всех проверим условия .

5. Если все условия в п.4 будут выполнены, то за приближенное решение системы (3.1) выберем либо , либо и закончим вычисления. Если хотя бы одно условие в п.4 не будет выполнено, перейдем к п.6.

6. Положим и перейдем к п.3.

Этот алгоритм можно записать геометрически.

Достаточное условие сходимости метода Зейделя для системы (3.1) имеет вид , .

Метод Некрасова.

Пусть СЛАУ задана в виде

(5.1)

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

(5.2)

Систему (5.2) можно записать компактно

, . (5.3)

Во-вторых, систему (5.3) будем решать стационарным методом Зейделя по формулам:

, , (5.4)

Алгоритм численной реализации метода Ньютона для решения системы (5.1) по формулам (5.4) может быть таким.

1. Выберем , например, ,

2. Положим .

3. Для всех вычислим .

4. Для всех проверим условия .

5. Если все условия в п.4 будут выполнены, то за приближенное решение системы (5.1) выберем либо , либо и закончим вычисления. Если хотя бы одно условие в п.4 не будет выполнено, перейдем к п.6.

6. Положим и перейдем к п.3.

Изложенный алгоритм можно записать геометрически.

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

Задания.

Коэффициенты при переменных и свободные члены в системе уравнений даны в виде расширенной матрицы