Системы числовых уравнений в арифметических пространствах

A = QR,

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

Определение 16.

 Матрица Q называется ортогональной, если для нее выполняется условие

   QT = Q−1 , то есть QQT = E .

Метод вращений

В этом методе матрица C, приводящая исходную систему n уравнений

Ax = b к системе с верхней  треугольной матрицей CAx = Cb ⇒ Bx = d , где

B = CA; d = Cb , получается последовательным обнулением элементов, лежащих ниже главной диагонали с помощью матриц элементарных вращений T_ij   Гивенса:

 

Они отличаются от единичной  матрицы E только четырьмя элементами:

.

Умножение вектора x на матрицу T_ij геометрически можно интерпретировать как поворот в плоскости Ox_i x_j n-мерного пространства, что и дало

название методу. Матрица  T_ij удовлетворяет условию ортогональности

.

На первом шаге прямого  хода, получения матрицы B, исключается переменная x₁ из второго и последующих уравнений исходной системы. Это делается посредством умножения слева системы Ax = b вначале на матрицу вращения

 

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

 

 

где a_ij – коэффициенты матрицы A. Коэффициенты t_ij удовлетворяют условиям:

.(5)

В результате получается система, второе уравнение которой не содержит неизвестное x₁ :

, (6)

Новые коэффициенты первых двух уравнений вычисляются по правилам:

 

 

согласно (5).

Если в исходной системе  a₂₁ =0 , считается t₁₁ =1, t₁₂ =0 , и матрица вращений становится равной единичной T₁₂ = E .

Для исключения x₁ из третьего уравнения система (6) умножается слева на матрицу вращения  T₁₃:

                 .

Коэффициенты T₁₃ вычисляются по формулам:

, (7)

и удовлетворяют условиям

 

Аналогичным образом исключается 1 x из всех последующих уравнений. В итоге получается система следующего вида:

     .

 

На втором шаге метода, состоящем из (n − 2) “малых” шагов, аналогичным образом исключается x₂ из третьего и последующих уравнений системы A⁽¹⁾x = b⁽¹⁾ .

После завершения (n −1) -го шага система принимает вид:  .

или в матричной форме:

.

Верхняя треугольная матрица  A⁽ⁿ⁻¹⁾ , которая обычно обозначается R, связана с исходной матрицей равенством R = TA, где T – матрица результирующего вращения,

 

Матрица T ортогональна, так как является произведением ортогональных матриц T_ij . Обозначая Q = T ⁻¹ = T^T , получаем

 

то есть QR-разложение матрицы A.

Обратный ход метода вращения проводится так же, как и в методе Гаусса, то есть решается вначале система Qy = b, а затем система Rx = y. Этот метод обладает существенной численной устойчивостью, однако более трудоемок в сравнении с методом Гаусса. Получение матриц QR-разложения для квадратной матрицы A порядка n общего вида требует около 2n³ арифметических операций.

Итерационные  методы.

Метод простой  итерации (Якоби).

Пусть задана система уравнений  Ax = b. Представим ее в виде x = Gx + β (8), где G – матрица; x, β – векторы.

 Зададим некоторое  начальное приближенное значение вектора x = x⁽⁰⁾ и подставим его в правую часть уравнения (8). В результате получим первое приближение вектора x⁽¹⁾ . Его снова подставим в правую часть уравнения (8), и получим второе приближение вектора x⁽²⁾ . Продолжая далее этот процесс, получим последовательность значений вектора {x^{(k )} }:

 

 

                                             ………………

 

Если последовательность векторов { x^{(k )} } сходится, то она сходится к решению системы уравнений. Покажем это. Из последовательностей (9) находим:

 

 

               …………………………………………………

 

Используя понятие нормы, величину вектора x можно оценить так:

.   (10)

Если норма матрицы  G меньше единицы ||G||<1, то , и первый член этого неравенства пропадает при любом начальном значении вектора x. Второй член неравенства при k →∞ равен

 

Для доказательства этого  утверждения умножим (G^k−1 +G^k−2 + …+ E) на (E−G). В результате получим

(G^k−1 + G^k−2 +…+ E)(E − G) = G^k−1 + G^k−2 +…+ E − G^k − G^k−1 −…− G = E − G^k ,

откуда . Так как , и , что и требовалось доказать.

Таким образом, неравенство (10) преобразуется к виду

 

С другой стороны, перенеся неизвестные в левую часть, уравнение  x = Gx + β можно записать в виде (E −G)x = b . Умножив его слева на обратную матрицу (E −G)−1 , получим решение системы

 

что совпадает с оценкой решения методом итераций (11) при k →∞. Таким образом, для сходимости процесса итераций необходимо, чтобы < 1. Причем сходимость в этом случае имеет место при произвольном начальном значении x⁽⁰⁾ .

Итерации продолжаются до выполнения условия

 

где ε – заданная погрешность расчета.

Число операций для получения  решения N ≈ 2n²k , где n – порядок системы; k – число итераций.

Метод Гаусса–Зейделя.

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

Пусть система Ax = b приведена к виду (8) x = Gx + β . Представим матрицу G в виде суммы трех матриц G = L + D + R, где D – диагональная матрица; L – нижняя треугольная матрица; R – верхняя треугольная матрица (без диагональных элементов). Тогда алгоритм метода Гаусса–Зейделя можно записать в виде

 

или в виде

 

где x^{(k )} , x^(k+1)– два последовательных приближения к точному решению,

k = 1, 2,… – номер итерации. Уравнения этой системы решаем последовательно друг за другом, используя ранее вычисленные компоненты вектора x^(k+1) . Итерации продолжаются до выполнения условия сходимости. Рассмотрим методы Якоби и Гаусса–Зейделя на примере решения системы трех уравнений:

 

Зададим произвольные начальные значения и подставим их в

правую часть системы (13). В результате получим следующие приближения

неизвестных: и т. д. до выполнения условия сходимости.

Алгоритм метода Гаусса–Зейделя также использует начальные значения вектора x и имеет следующий вид:

 

 

 

то есть отличается от метода простой итерации тем, что при  расчете компонент вектора x на (k +1)-й итерации используются все ранее вычисленные компоненты (k +1)-й итерации.

Условие сходимости метода Гаусса–Зейделя такое же, < 1, однако сходимость в общем случае более быстрая, чем у метода Якоби.

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

 

то есть матрица A системы Ax = b должна иметь диагональное преобладание.              

Приведем рассмотренные  итерационные методы в матричном  виде. Для этого представим матрицу A как сумму нижней треугольной, диагональной и верхней треугольной матриц A = L + D + R:

;                ;

 

 

Заменяя в уравнении Ax = b матрицу A суммой матриц A = L + D + R, представим алгоритмы Якоби и Гаусса–Зейделя соответственно в виде:

 

 

В правых частях этих уравнений  записаны уже известные компоненты вектора x.

Методы решения нелинейных уравнений.

Задачи вычисления корней нелинейных уравнений часто встречаются при научных исследованиях. Корнем, или решением нелинейного уравнения f (x) = 0 , (15) называется такое значение x =ξ , которое превращает уравнение (15) в тождество: f (ξ ) ≡ 0. Нелинейные уравнения обычно подразделяют на алгебраические и трансцендентные. Алгебраическими называются уравнения, содержащие алгебраические функции. Уравнения, содержащие тригонометрические, показательные, логарифмические и др. функции, называются трансцендентными.

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

Приближенное нахождение изолированных корней уравнения  обычно

состоит из двух этапов:

1) отделения корней, то  есть определения интервалов, содержащих отдельные корни;

2) уточнения приближенных  корней, т. е. доведения их до  заданной степени точности.

 

В общем случае систему нелинейных уравнений можно записать в виде:

 

Если неизвестные x₁, x₂, …, x_n и функции f₁, f₂,…, f_n рассматривать как n-мерные векторы , то систему (16) можно записать кратко в векторном виде  F(x)=0.

 

Метод половинного  деления.

Пусть требуется найти  корень уравнения f (x) = 0 на отрезке [a,b], который был задан заранее, либо получен методом отделения корней. Решение задачи выполняется следующим образом. Проверяется условие существования корня на отрезке [a,b]: f (a) f (b) < 0 . Если это условие выполнено, приступаем к вычислению корня. Отрезок делится пополам точкой c = (a + b) / 2 и вычисляется значение функции f (c) в этой точке. Проверяется, на каком из двух получившихся отрезков [a,c] или [c,b] располагается корень. Для этого следует определить знак произведения f(a)f(c) или f(c)f(b) . Если f(a)f(c) < 0, то f(c) f(b) > 0 , и корень располагается на отрезке [a,c]. Следовательно, отрезок [c,b] можно отбросить и искать корень на отрезке [a,c], который обозначается как [a₁ ,b₁ ] . В противном случае f(a)f(c) > 0 , корень располагается на отрезке [c,b] , и этот отрезок обозначается [ a₁,b₁ ]. С отрезком [ a₁,b₁ ] производятся точно такие же действия, как и с предыдущим, в результате чего получается отрезок [ a₂,b₂ ] вдвое меньшей длины, содержащий корень. В ходе повторных операций половинного деления получается последовательность вложенных друг в друга отрезков [ a₁,b₁ ], [ a₂,b₂ ],…, [a_n ,b_n ], таких, что f(a_n)f(b_n) < 0, и, следовательно, содержащих корень. Длина их уменьшается по закону

 

Процесс половинного деления  продолжается до тех пор, пока длина  отрезка [ a_n, b_n] не станет меньше заданной погрешности ε:

 

Cреднюю точку отрезка [a_n ,b_n ] можно принять за приближенное значение корня 

 

Из неравенства (17) можно определить число n операций половинного деления, необходимых для получения заданной точности решения:

 

Погрешность приближенного  решения можно оценить по формуле:

 

Пример

Методом половинного деления  уточнить корень уравнения

f(x) = x⁴ + 2 x³ - x - 1 = 0

лежащий на отрезке [ 0, 1] .

Последовательно имеем:

f(0) = - 1; f(1) = 1; f(0,5) = 0,06 + 0,25 - 0,5 - 1 = - 1,19;

f(0,75) = 0,32 + 0,84 - 0,75 - 1 = - 0,59;

f(0,875) = 0,59 + 1,34 - 0,88 - 1 = + 0,05;

f(0,8125) = 0,436 + 1,072 - 0,812 - 1 = - 0,304;

f(0,8438) = 0,507 + 1,202 - 0,844 - 1 = - 0,135;

f(0,8594) = 0,546 + 1,270 - 0,859 - 1 = - 0,043 и т. д.

Можно принять

ξ= (0,859 + 0,875) = 0,867

Метод Ньютона.

Формулы метода Ньютона для  систем нелинейных уравнений, как и  в случае одного нелинейного уравнения, получаются посредством применения формулы Тейлора для функции F(x) в окрестности решения ξ . Пусть нам известно некоторое k-е приближение x^{(k )} к решению ξ системы (16). Поэтому решение можно представить как

 

где Δx – приращение (поправка) к приближенному решению. В развернутом виде это уравнение записывается как

 

Разложим функцию F(x) в ряд Тейлора по малому параметру Δx, оставив только два первых члена разложения в силу малости параметра:

 

Здесь - матрица Якоби для системы уравнений

 

Полагая, что матрица Якоби W(x^{(k )} ) неособенная, разрешим уравнение (18) относительно вектора Δx:

 

Здесь W ⁻¹ (x^(k)) – обратная матрица матрицы Якоби.

Подставив значение приращения Δx в уравнение (17), получаем алго-

ритм метода Ньютона

 

Здесь вместо точного решения ξ системы (16) в левой части алгоритма (19) поставлено последующее приближение x^(k+1) к решению, так как значение приращения Δx получено из приближенного уравнения (18). При расчете по формуле (19) на каждом шаге итерации необходимо вычислять обратную матрицу W ⁻¹ (x^{(k )} ) при новых значениях x^{(k )}. Расчеты продолжаются до      выполнения условия сходимости решения, т.е. близости двух последовательных приближений

 

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

Пример.

Пусть требуется решить систему  двух нелинейных уравнений:

f(x,y) = 0; φ(x,y) = 0 .

При этом известно приближенное значение решения: x = a; y = b .

Введем векторы:

 

и составим матрицу Якоби  для системы F(z) = 0 :

 

 

 

Полагая, что det W ≠ 0 при x = a, y = b , вычисляем обратную матрицу W⁻¹ :

 

 

 

 

 

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

z^(k+1) = z^{(k )} −W⁻¹ (z^{(k )})F(z^{(k )})

или в развернутом виде

 

 

Выражения справа сначала  вычисляются при x = x(0) = a; y = y(0) = b. Дальнейшие уточнения решения продолжаются для k = 1, 2,K до выполнения условия (20).

 

 

 

 

Заключение.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованной литературы:

1. А.Г. Галканов. Числовые уравнения и тождества в понятиях, теоремах, методах, задачах и решениях.
2. http://dic.academic.ru/dic.nsf/enc_mathematics/275/АРИФМЕТИЧЕСКОЕ.
3. http://ru.wikipedia.org/wiki/Система_линейных_алгебраических_уравнений.