Метод простой итерации в матричной форме. Решение слау методом простой итерации

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

Рассмотрим, как данный метод реализуется при решении СЛАУ. Метод простой итерации имеет следующий алгоритм:

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

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

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

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

x - =β - +α*x -

Это можно сделать множеством способов, например, так: из первого уравнения выразить х 1 через другие неизвестные, из второго- х 2 , из третьего- х 3 и т.д. При этом используем формулы:

α ij = -(a ij / a ii)

i = b i /a ii
Следует снова убедиться, что полученная система нормального вида соответствует условию сходимости:

∑ (j=1) |α ij |≤ 1, при этом i= 1,2,...n

4. Начинаем применять, собственно, сам метод последовательных приближений.

x (0) - начальное приближение, выразим через него х (1) , далее через х (1) выразим х (2) . Общая формула а матричном виде выглядит так:

x (n) = β - +α*x (n-1)

Вычисляем, пока не достигнем требуемой точности:

max |x i (k)-x i (k+1) ≤ ε

Итак, давайте разберем на практике метод простой итерации. Пример:
Решить СЛАУ:

4,5x1-1.7x2+3.5x3=2
3.1x1+2.3x2-1.1x3=1
1.8x1+2.5x2+4.7x3=4 с точностью ε=10 -3

Посмотрим, преобладают ли по модулю диагональные элементы.

Мы видим что условию сходимости удовлетворяет лишь третье уравнение. Первое и второе преобразуем, к первому уравнению прибавим второе:

7,6x1+0.6x2+2.4x3=3

Из третьего вычтем первое:

2,7x1+4.2x2+1.2x3=2

Мы преобразовали исходную систему в равноценную:

7,6x1+0.6x2+2.4x3=3
-2,7x1+4.2x2+1.2x3=2
1.8x1+2.5x2+4.7x3=4

Теперь приведем систему к нормальному виду:

x1=0.3947-0.0789x2-0.3158x3
x2=0.4762+0.6429x1-0.2857x3
x3= 0.8511-0.383x1-0.5319x2

Проверяем сходимость итерационного процесса:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0.383+ 0.5319= 0.9149 ≤ 1 , т.е. условие выполняется.

0,3947
Начальное приближение х (0) = 0,4762
0,8511

Подставляем данные значения в уравнение нормального вида, получаем следующие значения:

0,08835
x (1) = 0,486793
0,446639

Подставляем новые значения, получаем:

0,215243
x (2) = 0,405396
0,558336

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

x (7) = 0,441091

Проверим правильность полученных результатов:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3.1*0,1880+2.3*0,441-1.1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

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

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

ВВЕДЕНИЕ

1.РЕШЕНИЕ СЛАУ МЕТОДОМ ПРОСТОЙ ИТЕРАЦИИ

1.1 Описание метода решения

1.2 Исходные данные

1.3 Алгоритм

1.4 Программа на языке QBasic

1.5 Результат работы программы

1.6 Проверка результата работы программы

2. УТОЧНЕНИЕ КОРНЯ МЕТОДОМ КАСАТЕЛЬНЫХ

2.1 Описание метода решения

2.2 Исходные данные

2.3 Алгоритм

2.4 Программа на языке QBasic

2.5 Результат работы программы

2.6 Проверка результата работы программы

3.ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ ПО ПРАВИЛУ ПРЯМОУГОЛЬНИКА

3.1 Описание метода решения

3.2 Исходные данные

3.3 Алгоритм

3.4 Программа на языке QBasic

3.5 Проверка результата работы программы

4.1 Общие сведения о программе

4.1.1 Назначение и отличительные особенности

4.1.2 Ограничения WinRAR

4.1.3 Системные требования WinRAR

4.2 Интерфейс WinRAR

4.3 Режимы управления файлами и архивами

4.4 Использование контекстных меню

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

Целью данной курсовой работы является разработка алгоритмов и программ для решения системы линейных алгебраических уравнений с помощью метода Гаусса; нелинейного уравнения с помощью метода хорд; для численного интегрирования по правилу трапеций.

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

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

· точные методы, представляющие собой конечные алгоритмы для вычисления корней системы (решение систем с помощью обратной матрицы, правило Крамера, метод Гаусса и др.),

· итерационные методы, позволяющие получить решение системы с заданной точностью путем сходящихся итерационных процессов (метод итерации, метод Зейделя и др.).

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

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

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

Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод известен в различных вариантах уже более 2000 лет. Метод Гаусса - классический метод решения системы линейных алгебраических уравнений (СЛАУ). Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе ступенчатого (или треугольного) вида, из которой последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные.

Строго говоря, описываемый выше метод правильно называть методом "Гаусса-Жордана" (Gauss-Jordan elimination), поскольку он является вариацией метода Гаусса, описанной геодезистом Вильгельмом Жорданом в 1887 г.). Также интересно заметить, что одновременно с Жорданом (а по некоторым данным даже раньше него) этот алгоритм придумал Класен (B.-I. Clasen).

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

Задача нахождения корня уравнения f(x) = 0 итерационным методом состоит из двух этапов:

· отделение корней - отыскание приближенного значения корня или содержащего его отрезка;

· уточнение приближенных корней - доведение их до заданной степени точности.

Определенным интегралом функции f(x), взятом в интервале от a до b , называется предел, к которому стремится интегральная сумма при стремлении всех промежутков ∆x i к нулю. Согласно правилу трапеций, необходимо заменить график функции F(x) прямой, проходящей через две точки (х 0 ,у 0) и (х 0 +h,у 1), и вычислить значение элемента интегральной суммы как площадь трапеции: .

РЕШЕНИЕ СЛАУ МЕТОДОМ ПРОСТОЙ ИТЕРАЦИИ

1.1 Описание метода постой итерации

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

или, при записи в матричной форме:

В практике используют два типа методов численного решения СЛАУ – прямые и косвенные. При использовании прямых методов СЛАУ приводится к одной из специальных форм (диагональной, треугольной) позволяющих точно получить искомое решение (если таковое существует). Наиболее распространенным прямым методом решения СЛАУ является метод Гаусса. Итерационные методы служат для поиска приближенного решения СЛАУ с заданной точностью. Следует отметить, что итерационный процесс не всегда сходится к решению системы, а только тогда, когда последовательность получаемых при расчетах приближений стремиться к точному решению. При решении СЛАУ методом простой итерации ее преобразуют к виду, когда в левой части находится только одна из искомых переменных:

Задав некоторые исходные приближения xi, i=1,2,…,n , подставляют их в правую часть выражений и вычисляют новые значения x . Процесс повторяют до тех пор, пока максимальная из невязок, определяемых по выражению:

не станет меньше заданной точности ε. Если максимальная невязка при k -ой итерации окажется больше максимальной невязки при k-1 -ой итерации, то процесс аварийно завершают, т.к. итерационный процесс расходится. Для минимизации количества итераций новые значения x можно вычислять с использованием значением невязок на предыдущей итерации.

Лекция Итерационные методы решения системы алгебраических линейных уравнений.

Условие сходимости итерационного процесса.Метод Якоби.Метод Зейделя

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

Рассматривается система линейных алгебраических уравнений

Для применения итерационных методов система должна быть приведена к эквивалентному виду

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

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

Метод Якоби .

Самый простой способ приведения системы к виду, удобному для итерации, состоит в следующем:

Из первого уравнения системы выразим неизвестное x 1 , из второго уравнения системы выразимx 2 , и т. д.

В результате получим систему уравнений с матрицей B, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам:

Компоненты вектора d вычисляются по формулам:

Расчетная формула метода простой итерации имеет вид:

или в покоординатной форме записи выглядит так:

Критерий окончания итераций в методе Якоби имеет вид:

Если
, то можно применять более простой критерий окончания итераций

Пример 1. Решение системы линейных уравнений методом Якоби.

Пусть дана система уравнений:

Требуется найти решение системы с точностью

Приведем систему к виду удобному для итерации:

Выберем начальное приближение, например,

- вектор правой части.

Тогда первая итерация получается так:

Аналогично получаются следующие приближения к решению.

Найдем норму матрицы B.

Будем использовать норму

Так как сумма модулей элементов в каждой строке равна 0.2, то
, поэтому критерий окончания итераций в этой задаче

Вычислим нормы разностей векторов:

Так как
заданная точность достигнута на четвертой итерации.

Ответ: x 1 = 1.102, x 2 = 0.991, x 3 = 1.0 1 1

Метод Зейделя .

Метод можно рассматривать как модификацию метода Якоби. Основная идея состоит в том, что при вычислении очередного (n+1) -го приближения к неизвестномуx i приi >1 используют уже найденные(n+1)- е приближения к неизвестнымx 1 ,x 2 , ...,x i - 1 , а неn -ое приближение, как в методе Якоби.

Расчетная формула метода в покоординатной форме записи выглядит так:

Условия сходимости и критерий окончания итераций можно взять такими же, как в методе Якоби.

Пример 2. Решение систем линейных уравнений методом Зейделя.

Рассмотрим параллельно решение 3-х систем уравнений:

Приведем системы к виду удобному для итераций:

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

1-ая система:

Точным решением будут значения: x 1 = 1.4, x 2 = 0.2 . Итерационный процесс сходится.

2-ая система:

Видно, что итерационный процесс расходится.

Точное решение x 1 = 1, x 2 = 0.2 .

3-я система:

Видно, что итерационный процесс зациклился.

Точное решение x 1 = 1, x 2 = 2 .

Пусть матрица системы уравнений A – симметричная и положительно определенная. Тогда при любом выборе начального приближения метод Зейделя сходится. Дополнительных условий на малость нормы некоторой матрицы здесь не накладывается.

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

Если A – симметричная и положительно определенная матрица, то систему уравнений часто приводят к эквивалентному виду:

x =x -τ (Ax - b), τ – итерационный параметр.

Расчетная формула метода простой итерации в этом случае имеет вид:

x (n+1 ) =x n - τ (Ax (n ) - b).

и параметр τ > 0 выбирают так, чтобы по возможности сделать минимальной величину