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

Итерационные методы решения СЛАУ. Метод простых итераций. Метод Зейделя.

Введение

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

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

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

1. Приведение исходной системы вида к итерационной форме.
2. Проверка условия сходимости.
3. Решение системы одним из методов.

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

Теперь, опираясь на представленную последовательность, разберем метод простых итераций. Сразу условимся, что для общего вида систем выполняется тождество m=n, где m — количество уравнений в системе, n — количество неизвестных. Т.е. не имеет смысла решать недоопределенные (m n) системы, т.к. они могут быть сведены путем элементарных алгебраических преобразований к нормальным (m=n) системам линейных уравнений. Другими словами, если у вас имеется «ненормальная» система, то прежде, чем использовать метод простых итераций, преобразуйте ее к нормальной.

Все мы знаем, что система линейных уравнений может быть записана в матричной форме, где A – матрица коэффициентов, b – вектор свободных членов, x – вектор неизвестных. Возьмем систему:

Ее матричная форма:

Смотрим на первый этап итерационных методов – он предполагает преобразование исходной системы, а именно матрицы А и вектора b к итерационной форме, где С и d – итерационные формы исходных данных.

Переход к итерационному виду осуществляется по следующим формулам:

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

В итоге для нашей системы должно получиться:

Проверьте. Ошибка? Если считать по исходной системе, то да. Все дело в том, что я не сказал про одно «НО».

Это «НО» заключается в следующем. Если мы будем преобразовывать исходную систему к итерационной форме, то она не удовлетворит условию сходимости:

Некоторые элементы матрицы C будут больше единицы. А глядя на условие сходимости, становится понятно, что, если хотя бы один будет больше единицы, то условие не выполнится, и решение системы путем простых итераций не будет найдено.

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

Смотрим нашу начальную систему. Видим, что третий элемент третьей строки по модулю больше других. Оставим его неизменным. Меняем местами первую и вторую строки. Теперь умножаем строку, ставшую первой, на -1 и складываем с новой второй. В итоге получаем:

Теперь при подстановке в формулы мы получим итерационную форму верно. К сожалению, это преобразование начальной системы к «благоприятному» виду — чистая аналитика, поэтому записать его в программный код очень сложно, а если даже и попытаться, то в некоторых случаях вероятно возникновение ошибок.

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

В конечном счете, мы получили систему линейных алгебраических уравнений в итерационной форме:

где x₁, x₂, x₃ – приближения, получаемые на текущей итерации за счет приближений полученных на предыдущей итерации — x 0 ₁, x 0 ₂, x 0 ₃.

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

Я думаю, что теории достаточно, осталось лишь обратить внимание на программную реализацию метода.

Далее представлен код, написанный в среде PascalABC.Net. Эта система была выбрана мной благодаря возможности работать с динамическими массивами (в Turbo Pascal предусмотрены только статические). Поэтому программа может решать любую нормальную систему линейных уравнений, которая проходит проверку условия сходимости. Главное, чтобы вид этой системы соответствовал вышеописанным критериям.

Применимо к нашей СЛАУ программа выдаст ответ: x₁=1.0000002, x₂=2.000000009, x₃=-1.0000002. Такой вектор приближений соответствует точности 10 -6 , прописанной в коде.

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

Как я уже говорил, метод простых итераций и метод Зейделя почти идентичны. Разница лишь в том, что в методе Зейделя расчет вектора приближений на текущей итерации происходит с использованием данных, полученных ни только на предыдущей, но и на нынешней итерации. То есть элемент x₁ вычисляется на основе x₂ и x₃, значения которых, расчитаны на предыдущей итерации, а следующий элемент x₂ уже вычисляется за счет x₁, полученного именно на текущей итерации, и x₃ на предыдущей. Другими словами данные в методе Зейделя для расчета вектора X поступают в процесс по мере их вычисления. А в методе простых итераций используются данные, строго полученные на предыдущей итерации.

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

И на последок покажем это различие в практической реализации. Чтобы метод простых итераций «превратился» в метод Зейделя нужно поменять процедуру ProstIterMetode, например, на следующую:

Программа решения системы линейных уравнений методом итераций. Разработка Pascal-программы. Блок-схема алгоритма и его описание

Страницы работы

Фрагмент текста работы

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

Очень часто для ускорения сходимости в итерационные методы вводят числовые параметры t_k , которые зависят, вообще говоря, от номера итераци. Способ выбора итерационных параметров определяется при

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

Канонической формой одношагового итерационного метода решения СЛАУ называется его запись в виде

где B_k+1 — матрица, задающая тот или иной итерационный метод, t_k+1 — итерационный параметр. Предполагается, что существуют обратные матрицы [B_k+1] -1 . Итерационный метод называют явным, если стационарным, ес B_k+1 — единичная матрица. Неявные итерационные методы имеет смысл применять лишь в том случае, когда каждую матрицу B_k обратить легче, чем исходную матрицу A (т. е. когда решение системы уравнений с матрицей B_k требует меньше машинной памяти или времени или алгоритмически проще, чем решение исходной системы).

Итерационный метод называется ecли B_k+1=B и t_k+1=t, (т.е. не зависят от номера итерации), и нестационарным — в противоположном случае. Согласно этой классификации метод простой итерации является одношаговым явным стационарным методом с диагональной матрицей B (b_ii.= a_ii) и может быть записан в виде , где r ( k ) — вектор невязки.

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

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

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

итерационного метода выполняются оценки

, где qÎ (0,1), то говорят, что метод сходится со скоростью геометрической прогрессии со знаменателем q. Можно определить число итераций, достаточное для того, чтобы начальная погрешность уменьшилась в заданное число раз, потребовав, чтобы q n i then s:=s-an[i,j]*x0[j];

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

Матвеева Антонина Гавриловна №241-922-342

Учитель информатики МОУ СОШ №17 с углубленным изученим математики г. Тверь

Разработка программы на языке программирования Паскаль «Решения системы линейных уравнений» разными методами.
С одержание

1.1 Метод Гаусса 4

1.2 Матричный метод 5

1.3 Вычисление определителей второго и третьего порядка 6

1.4 Решение системы линейных уравнений с тремя неизвестными методом Крамера 8

2. Описание программы 9

2.1 Работа программы 9

2.2 Блок-схема программы 10

1. Описание математических методов решения систем линейных уравнений

1.1 Метод Гаусса

Пример 1.

Выбирается ведущее уравнение с коэффициентом при х₁, равным 1. В нашем примере ведущим уравнением будет второе. Систему лучше переписать, поставив это уравнение на первое место:

Умножаем первое уравнение на 6 и вычитаем из полученного второе, чтобы исключить из второго неизвестное х₁. Первое уравнение записываем, а на место второго — результат вычитания.

Затем первое уравнение умножим на 3 и складываем с третьим уравнением. Тогда получаем систему

Или

первое уравнение переписываем без изменения, а второе умножаем на 7 и вычитаем из него третье уравнение, умноженное на 15, чтобы избавиться от х₂ в третьем уравнении. При этом второе записываем без изменения, на месте третьего — результат вычитания. Тогда

Из третьего следует х₃ =-3, подставим его во второе, получим х₂ = — 2. Далее подставим найденные х₂ и х₃ в первое уравнение, получим х₁ = 1.

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

1.2 Матричный метод

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

Составим матрицу из коэффициентов при неизвестных

А =

Введем в рассмотрение матрицы — столбцы для неизвестных и свободных членов:

Х = ; В = .

Тогда систему (2) можно переписать в матричной форме

Умножив это уравнение на слева, получим , откуда =или

Следовательно, матрица — решение Х находится как произведение на В.

Пример 2. Решить систему уравнений матричным методом

Решение: определитель матрицы

А=
∆=-1, значит, существует обратная матрица .

Матрица — столбец при неизвестных:

Х =

Матрица — столбец из свободных членов:

В =
Тогда решение запишется в виде
==
Откуда следует, х₁ = 1; х₂ = 0; х₃ = 2.

1.3 Вычисление определителей второго и третьего порядка

Число (а₁₁ а₂₂ — а₁₂ а₂₁) называется определителем второго порядка и обозначается символом

Определитель второго порядка содержит две строки и два столбца. Числа а₁₁, а₁₂, а₂₁, а₂₂ называются элементами определителя. Диагональ определителя, на которой расположены числа а₁₁, а₂₂ — главная, а элементы а₁₂, а₂₁ составляют побочную диагональ.

Определитель 3-го порядка содержит три строки и три столбца:

Для вычисления определителя третьего порядка существует несколько способов.

Рассмотрим метод вычисления определителя разложением по элементам первой строки.

Введем понятие минора и алгебраического дополнения.

Минором некоторого элемента определителя называется определитель, полученный из данного вычеркиванием той строки и того столбца в которых этот элемент расположен. Обозначается М_{ij (}i — номер строки, j — номер столбца).

Например, минором элемента а₁₂ является определитель

Алгебраическим дополнением данного элемента определителя называется его минор, умноженный на (-1) i + j . Алгебраические дополнения обозначаются буквами А_ij, и тогда А_y= (-1) i + j M_y.

Определитель вычисляется так:

=.
Так же можно разложить определитель по любой строке или столбцу.

Изложенный метод применим к вычислению определителей 4-го и т.д. порядков.

Пример3. Вычислить определитель разложением по элементам первой строки

Решение: Элементы первой строки

А₁₁ = (-1) 1+1 . М₁₁==4+1=5.

М₁₁ получили, вычеркнув первую строку и первый столбец.
А₁₂ = (-1) 1+2 . М₁₂= — = — (8+3) = — 11.
М₁₂ получили, вычеркнув первую строку и второй столбец.
А₁₃ = (-1) 1+3 . М₁₃ = = 2-3 = — 1.
М₁₃ получили, вычеркнув первую строку и третий столбец.

= 1.5+2. (-11) — 2. (-1) = — 15

1.4 Решение системы линейных уравнений с тремя неизвестными методом Крамера

2. Описание программы

2.1 Работа программы

Для решения систем линейных уравнений методом Гаусса и матричным методом создана программа на языке Паскаль. Программа запрашивает исходные данные (рис.1):

матрицу коэффициентов при неизвестных х;

столбец свободных членов

способ решения системы линейных уравнений — вариант 1 или 2.

Рисунок 3.1 Ввод исходных данных

В зависимости от выбранного вариант в программе происходит решение системы уравнений методом Гаусса (рис.2) или матричным методом (рис.3) с выдачей на экран результатов:

Рисунок 3.2 Результаты расчетов системы линейных уравнений методом Гаусса.

Рисунок 3.3 Результаты расчетов системы линейных уравнений матричным методом.
Программа состоит из 7 подпрограмм — 6 процедур и одной функции:

процедура Gauss обеспечивает решение системы линейных уравнений по методу Гаусса;

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

процедура PrintMatr2 предназначена для выдачи на экран исходной и обратной матрицы;

процедура MultString предназначена для умножения строк матрицы на число r;

процедура AddStrings прибавляет к i1-ой строке матрицы i2-ю, умноженную на число r;

процедура MultMatr предназначена для умножения матриц.

Функция Sign используется для изменения знака на противоположный при вычислении обратной матрицы.

Программа настроена на решение системы 3-х линейных уравнений с тремя неизвестными. Чтобы решить систему из 2-х уравнений с 2-мя неизвестными необходимо в программе изменить значение константы N с N=3 на N =2 (рис.4).

Рисунок 3.4. Фрагмент программы с описанием констант и переменных.