Точные и итерационные методы решения систем уравнений

Итерационные методы решения систем уравнений установившегося режима

Общая характеристика методов

Методы решения систем уравнений — прямые (точные) и итерационные (приближенные). Прямые применяются для решения систем линейных урав-нений, итерационные — для решения систем линейных и нелинейных уравне-ний.

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

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

Итерациями называются многократно повторяющиеся однотипные ша-ги вычислений.

Основные характеристики итерационных методов:

1. Условия сходимости к решению, при которых происходит приближе-ние к искомому решению U (*) , либо удаление от него;

2. Скорость сходимости. Характеризуется количеством итераций n, необ-ходимых для достижения решения с заданной точностью, или законом изменения вектора погрешности при переходе от итерации к итерации;

2.3. Характер сходимости. Сходимость – апе-риодическая или колебательная.

Возможно влияние на скорость сходимос-ти за счет введения дополнительных коэффици-ентов;

4. Необходимость хранения в памяти ЭВМ всех коэффициентов систем уравнений. Удобство программирования, простота алгоритмов и т.д.

Рассматриваем систему нелинейных уравнений установившегося режи-ма. В матричной форме она имеет вид:

(1)

В развернутой форме такая система уравнений может быть представлена в следующем виде:

(2)

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

(3)

Любое i-ое уравнение этой системы можно записать в общем виде:

(4)

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

(4а)

В матричной форме система (3) может быть записана следующим образом:

здесь — вектор неизвестных напряжений;

D — вектор свободных членов, ;

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

В итерационном виде система (5) принимает вид:

. (6)

Здесь к – номер приближения неизвестных.

Общий алгоритм итерационных методов решения СНАУ установившегося режима

1) Задание начальных приближений вектора неизвестных U (0) =U_ном.

Как правило, в качестве начальных приближений напряжений задают номи-нальные напряжения узлов U_ном.В некоторых случаях, в качестве начальных приближений напряжений принимают значения, полученные в предыдущих близких расчетах для данной схемы;

2) Задание точности расчета E, предельного количества итераций n_пред.,

начального значения счетчика итераций к=0 и других параметров расчета;

3) Выполнение итерации в соответствии с формулой (6):

;

4) Контроль завершения итерационного процесса:

Если условие не выполняется, то изменяем счетчик итераций (к=к+1) и возвращаемся к пункту (3). Повторяем расчет при новых приближениях неизвестных.

Если условие выполняется для всех значений U_i, то итерационный процесс завершается, найденные на последней итерации приближения неизвестных U ( k +1) принимаются в качестве искомых значений с заданной точностью.

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

(7)

здесь U (* ) — точное решение при .

Таким образом, точное решение может быть получено лишь в резуль-тате бесконечного итерационного процесса. Всякий вектор U ( k ) , полученный на к-ой итерации, является приближенным решением системы уравнений.

Вектор погрешности этого приближенного решения:

(8)

Так как точное решение U (*) заранее неизвестно, то о погрешности судят по разности значений на смежных итерациях (к+1) и к, то есть по вектору поправок:

(9)

Если для всех і, то итерационный процесс завершается.

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

Более строгим и надежным способом контроля завершения итераци-онных процессов является контроль невязок уравнений. Невязка уравнения – разность между левой и правой частями уравнения. Её значение получаем при подстановке в уравнения системы (2) очередного приближения неиз-вестных. Например, для 1-го уравнения:

. (10)

Для УУР невязка уравнения соответствует расчетному небалансу тока (мощ-ности) в узле. При подстановке точных значений неизвестных U₁ (*) ,U₂ (*) ,…,U_n (*) невязки будут равны нулю:

.

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

(11)

Итерационный процесс сошелся, если выполняются условия завершения итерационного процесса:

(12)

Это условие является более надежным критерием окончания итерационного процесса.

Достаточным условием сходимости итерационного процесса для урав-нений установившегося режима является:

Т.о. условие сходимости определяется только соотношением элементов матрицы проводимостей Y . В ней диагональные элементы У_іі (собственные проводимости узлов) неравны нулю. Как правило, диагональные элементы матрицы проводимостей больше или равны суммы недиагональных элемен-тов. Т.е. при правильном формировании матрицы, это условие сходимости выполняется всегда.

Два вида сходимости итерационных процессов:

1. Экспоненциальный (апериодический):

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

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

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

В данной статье мы расскажем общие сведения об итерационных методах решения СЛАУ, познакомим с методом Зейделя и Якоби, а также приведем примеры решения систем линейных уравнений при помощи данных методов.

Общие сведения об итерационных методах или методе простой итерации

Метод итерации — это численный и приближенный метод решения СЛАУ.

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

Рассмотрим систему A x = b .

Чтобы применить итерационный метод, необходимо привести систему к эквивалентному виду x = B x + d . Затем выбираем начальное приближение к решению СЛАУ x ( 0 ) = ( x 1 0 , x 2 0 , . . . x m 0 ) и находим последовательность приближений к корню.

Для сходимости итерационного процесса является достаточным заданное условие В 1 . Окончание итерации зависит от того, какой итерационный метод применили.

Метод Якоби

Метод Якоби — один из наиболее простых методов приведения системы матрицы к виду, удобному для итерации: из 1-го уравнения матрицы выражаем неизвестное x 1 , из 2-го выражаем неизвестное x 2 и т.д.

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

b i j = — a i j / a i i , i , j = 1 , 2 . . . , n

Элементы (компоненты) вектора d вычисляются по следующей формуле:

d i = b i / a i i , i = 1 , 2 , . . . , n

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

x ( n + 1 ) = B x ( x ) + d

Матричная запись (координатная):

x i ( n + 1 ) = b i 1 x n 1 + b i 2 x ( n ) 2 + . . . + b

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

x ( n + 1 ) — x ( n ) ε 1 , где ε 1 = 1 — B B ε

В случае если B 1 / 2 , то можно применить более простой критерий окончания итераций:

x ( n + 1 ) — x ( n ) ε

Решить СЛАУ методом Якоби:

10 x 1 + x 2 — x 3 = 11 x 1 + 10 x 2 — x 3 = 10 — x 1 + x 2 + 10 x 3 = 10

Необходимо решить систему с показателем точности ε = 10 — 3 .

Приводим СЛАУ к удобному виду для итерации:

x 1 = — 0 , 1 x 2 + 0 , 1 x 3 + 1 , 1 x 2 = — 0 , 1 x 1 + 0 , 1 x 3 + 1 x 3 = 0 , 1 x 1 — 0 , 1 x 2 + 1

Выбираем начальное приближение, например: x ( 0 ) = 1 , 1 1 1 — вектор правой части.

В таком случае, первая итерация имеет следующий внешний вид:

x 1 ( 1 ) = — 0 , 1 × 1 + 0 , 1 × 1 + 1 , 1 = 1 , 1 x 2 ( 1 ) = — 0 , 1 × 1 , 1 + 0 , 1 + 1 = 0 , 99 x 3 ( 1 ) = 0 , 1 × 1 , 1 — 0 , 1 × 1 + 1 = 1 , 01

Аналогичным способом вычисляются приближения к решению:

x ( 2 ) = 1 , 102 0 , 991 1 , 011 , x ( 3 ) = 1 , 102 0 , 9909 1 , 0111 , x ( 4 ) = 1 , 10202 0 , 99091 1 , 01111

Находим норму матрицы В , для этого используем норму B ∞ .

Поскольку сумма модулей элементов в каждой строке равна 0,2, то B ∞ = 0 , 2 1 / 2 , поэтому можно вычислить критерий окончания итерации:

x ( n + 1 ) — x ( n ) ε

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

x ( 3 ) — x ( 2 ) ∞ = 0 , 002 , x ( 4 ) — x ( 3 ) ∞ = 0 , 00002 .

Поскольку x ( 4 ) — x ( 3 ) ∞ ε , то можно считать, что мы достигли заданной точности на 4-ой итерации.

x 1 = 1 , 102 ; x 2 = 0 , 991 ; x 3 = 1 ,01 1 .

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

Метод Зейделя — метод является модификацией метода Якоби.

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

x i ( n + 1 ) = b i 1 x 1 ( n + 1 ) + b i 2 x 2 ( n + 1 ) + . . . + b i , i — 1 x i — 2 ( n + 1 ) + b i , i + 1 x i + 1 ( n ) +

+ . . . + b i m x m ( n ) + d i

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

Решить СЛАУ методом Зейделя. Пусть матрица системы уравнений А — симметричная и положительно определенная. Следовательно, если выбрать начальное приближение, метод Зейделя сойдется. Дополнительных условий на малость нормы некоторой матрицы не накладывается.

Решим 3 системы уравнений:

2 x 1 + x 2 = 3 x 1 — 2 x 2 = 1 , x 1 + 2 x 2 = 3 2 x 1 — x 2 = 1 , 2 x 1 — 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1

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

x 1 ( n + 1 ) = — 0 , 5 x 2 ( n ) + 1 , 5 x 2 ( n + 1 ) = 0 , 5 x 1 ( n + 1 ) + 0 , 5 , x 1 ( n + 1 ) = — 2 x 2 ( n ) + 3 x 2 ( n + 1 ) = 2 x 1 ( n + 1 ) — 1 , 2 x 1 — 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1 .

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

Вычисляем 3 первых приближения к каждому решению:

1-ая система: x ( 0 ) = 1 , 5 — 0 , 5 , x ( 1 ) = 1 , 75 0 , 375 , x ( 2 ) = 1 , 3125 0 , 1563 , x ( 3 ) = 1 , 4219 0 , 2109

Решение: x 1 = 1 , 4 , x 2 = 0 , 2 . Итерационный процесс сходится.

2-ая система: x ( 0 ) = 3 — 1 , x ( 1 ) = 5 9 , x ( 2 ) = — 15 — 31 , x ( 3 ) = 65 129

Итерационный процесс разошелся.

Решение: x 1 = 1 , x 2 = 2

3-я система: x ( 0 ) = 1 , 5 2 , x ( 1 ) = 2 — 6 , x ( 2 ) = 0 2 , x ( 3 ) = 0 2

Итерационный процесс зациклился.

Решение: x 1 = 1 , x 1 = 2

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

Если А — симметричная и положительно определенная, то СЛАУ приводят к эквивалентному виду:

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

Расчетная формула имеет следующий внешний вид:

x ( n + 1 ) = x ( n ) — τ ( A x n — b ) .

Здесь B = E — τ A и параметр τ > 0 выбирают таким образом, чтобы по возможности сделать максимальной величину B 2 .

Пусть λ m i n и λ m a x — максимальные и минимальные собственные значения матрицы А .

τ = 2 / ( λ m i n + λ m a x ) — оптимальный выбор параметра. В этом случае B 2 принимает минимальное значение, которое равняется ( λ m i n + λ m a x ) / ( λ m i n — λ m a x ) .

Различие между прямыми и итерационными методами численного решения задач. Примеры

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

При решении СЛАУ возникает необходимость выбора того или иного метода, который позволит получить эффективный результат с использованием вычислительной техники. В этой ситуации актуализируется проблема сравнительного анализа прямых и итерационных методов решения СЛАУ.

Таким образом, критериями сравнения точных и итерационных методов решения СЛАУ с использованием вычислительной техники будут:

-область применения метода;

-временные затраты на решение;

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

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

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

Отделение корней можно выполнить графически, если удается построить график функции

Уточнение корней. На данном этапе задача состоит в получении приближенного значения корня, принадлежащего отрезку , с заданной точностью (погрешностью) . Это означает, что вычисленное значение корня должно отличаться от точного не более чем на величину :

.

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

Дата добавления: 2015-02-16 ; просмотров: 43 | Нарушение авторских прав