Реферат: Методы решения алгебраических уравнений

--PAGE_BREAK--Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение xn в предпоследнее уравнение, получим xn–1. Осуществляя обратную подстановку, далее последовательно находим xn–1, xn–2, …, x1. Вычисления неизвестных здесь проводятся по формулам
xn = bn(n–1) / ann(n–1),
xk = (bn(k–1) – ak,k+1(k–1)xk+1 –  – akn(k–1)xn) / akk(k–1), (k = n – 1, 1).
Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы akk(k–1). Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.
Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора). Описание метода. На k-м шаге прямого хода коэффициенты уравнений системы с номерами i = k + 1, …, n преобразуются по формулам
aij(k) = aij(k–1) − qikakj, bi(k) = bi(k–1) − qikbk(k–1), i = k + 1, …, n.

Интуитивно ясно, что во избежание сильного роста коэффициентов системы и связанных с этим ошибок нельзя допускать появления больших множителей qik.
В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что |qik| ≤ 1 для всех k = 1, 2, …, n – 1 и i = k + 1, …, n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент aikk при неизвестной xk в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером ik меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента akk(k-1). После этой перестановки исключение неизвестного xk производят, как в схеме единственного деления.
Метод Гаусса с выбором главного элемента по всей матрице (схема полного выбора). В этой схеме допускается нарушение естественного порядка исключения неизвестных.
На 1-м шаге метода среди элементов aij определяют максимальный по модулю элемент ai1j1. Первое уравнение системы и уравнение с номером i1 меняют местами. Далее стандартным образом производят исключение неизвестного xi1 из всех уравнений, кроме первого.
На k-м шаге метода среди коэффициентов aij(k–1) при неизвестных в уравнениях системы с номерами i = k, …, n выбирают максимальный по модулю коэффициент aikjk(k-1). Затем k-е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное xjk из уравнений с номерами i = k + 1, …, n.
На этапе обратного хода неизвестные вычисляют в следующем порядке: xjn, xjn–1, …, xj1.

3. Метод Зейделя 3.2.1. Приведение системы к виду, удобному для итераций. Для того чтобы применить метод Зейделя к решению системы линейных алгебраических уравнений Ax = b
с квадратной невырожденной матрицей A, необходимо предварительно преобразовать эту систему к виду
x = Bx + c.
Здесь B – квадратная матрица с элементами bij (i, j = 1, 2, …, n), c – вектор-столбец с элементами cij (i = 1, 2, …, n).
В развернутой форме записи система имеет следующий вид:
x1 = b11x1 + b12x2 + b13x3 + … + b1nxn + c1
x2 = b21x1 + b22x2 + b23x3 + … + b2nxn + c2
xn = bn1x1 + bn2x2 + bn3x3 + … + bnnxn + cn
Вообще говоря, операция приведения системы к виду, удобному для итераций, не является простой и требует специальных знаний, а также существенного использования специфики системы.
Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы выразим неизвестное x1:
x1 = a11–1 (b1 – a12x2 – a13x3 – … – a1nxn),
из второго уравнения – неизвестное x2:

x2 = a21–1 (b2 – a22x2 – a23x3 – … – a2nxn),
и т. д. В результате получим систему
x1 = b12x2 +b13x3 +… +b1,n–1xn–1 +b1nxn+c1,
x2 = b21x1 +b23x3 +… +b2,n–1xn–1 +b2nxn+c2,
x3 = b31x1 +b32x2 +… +b3,n–1xn–1 +b3nxn+c3,
xn = bn1x1 +bn2x2 +bn3x3 +… +bn,n–1xn–1 +cn,
в которой на главной диагонали матрицы B находятся нулевые элементы. Остальные элементы выражаются по формулам
bij = –aij / aii, ci = bi / aii (i, j = 1, 2, …, n, j ≠ i)
Конечно, для возможности выполнения указанного преобразования необходимо, чтобы диагональные элементы матрицы A были ненулевыми.
Описание метода. Введем нижнюю и верхнюю треугольные матрицы
<line id="_x0000_s1026" from=«147.6pt,12.6pt» to=«154.8pt,12.6pt» o:allowincell=«f»><img width=«11» height=«2» src=«dopb408117.zip» v:shapes="_x0000_s1026">000…00b12b13…b1n
B1 =b2100…0B2 =00b23…b2n
b31b320…0, 000…b3n
bn1bn2bn3…0000…0
Заметим, что B =B1+B2 и поэтому решение x исходной системы удовлетворяет равенству
x = B1x + B2x + c.

Выберем начальное приближение x(0) = [x1(0), x2(0), …, xn(0)]T. Подставляя его в правую часть равенства при верхней треугольной матрице B2и вычисляя полученное выражение, находим первое приближение
x(1) = B1x(0) + B2x(1)
Подставляя приближение x(1), получим
x(2) = B1x(1) + B2x(2)
Продолжая этот процесс далее, получим последовательность x(0), x(1), …, x(n), … приближений к вычисляемых по формуле
x(k+1) = B1(k+1) + B2(k) + c
или в развернутой форме записи
x1(k+1) =b12x2(k) +b13x2(k) +… +b1nxn(k) +c1,
x2(k+1) =b21x1(k+1) +b23x3(k) + … +b2nxn(k) +c2,
x3(k+1) =b31x1(k+1) +b32x2(k+1) +… +b3nxn(k) +c3,
xn(k+1) =bn1x1(k+1) +bn2x2(k+1) +bn3x3(k+1) +… +cn.
Объединив приведение системы к виду, удобному для итераций и метод Зейделя в одну формулу, получим
xi(k+1) = xi(k) – aii–1(∑j=1i–1 aijxj(k+1) + ∑j=1n aijxi(k) – bi).
Тогда достаточным условием сходимости метода Зейделя будет

∑j=1, j≠i n | aij | < | aii |
(условие доминирования диагонали).
Метод Зейделя иногда называют также методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений.
4. Метод Жордана — Гаусса.
Схема с выбором главного элемента состоит в том, что требование неравенства нулю диагональных элементов akk, на которые происходит деление в процессе исключения, заменятся более жестким: из всех элементов К-го столба выбрать наибольший по модулю и переставить уравнения так, чтобы этот элемент оказался на месте элемента акк. Выбор главного элемента и связанная с ним перестановка строк необходимы в тех случаях, когда на каком-либо i-ом шаге акк=0 либо же акк очень мало по остальными элементами i- го столбца: при делении на такое «малое» акк будут получаться большие числа с большими абсолютными погрешностями, в результате чего решение может сильно исказиться.
Ниже излагается алгоритм полного исключения неизвестных или метод Жордана – Гаусса. Суть метода состоит в том, что, рассмотрев первое уравнение, в нем неизвестное с коеффициэнтом, отличным от нуля (в дальнейшем разрешающий элемент ), и разделив первое уравнение на этот коэффициент, с помощью первого уравнения исключают это неизвестное из всех уравнений, кроме первого. Выбрав во втором уравнении неизвестное с коэффициентом, отличным от нуля, и разделив на него второе уравнение, с помощью второго исключают другие неизвестные из всех уравнений, кроме второго и т.д., т.е. с помощью одного уравнения производят полное исключение одного неизвестного. Процесс продолжается до тех пор, пока не будут использованы все уравнения.
Как известно, системы линейных алгебраических уравнений могут имеет одно решение, множество решений или системы несовместны. При элементарных преобразованиях элементов матрицы системы эти случаи выявляются в следующем:
1. В процессе исключений левая часть I –го уравнения системы обращается в нуль, а правая часть равна некоторому числу, отличному от нуля. т.е. 0<shape id="_x0000_i1052" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image036.wmz» o:><img width=«56» height=«23» src=«dopb408118.zip» v:shapes="_x0000_i1052">2+<shape id="_x0000_i1053" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image038.wmz» o:><img width=«61» height=«24» src=«dopb408119.zip» v:shapes="_x0000_i1053">=bc<shape id="_x0000_i1054" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image040.wmz» o:><img width=«15» height=«15» src=«dopb408120.zip» v:shapes="_x0000_i1054">0.
Это означает, что система не имеет решений, так как I – му уравнению не могут удовлетворять никакие значения неизвестных;
2. Левая и правая части I – го уравнения обращаются в нуль. Это означает, что I – ое уравнение является линейной комбинацией остальных, ему удовлетворяет любое найденное решение системы, поэтому оно может быть отброшено. В системе количество неизвестных больше количества уравнений и, следовательно, такая система имеет множество решений;
3. После того как все уравнения использованы для исключения неизвестных получено решение системы.
Таким образом, конечной целью преобразований Жордана-Гаусса является получение из заданной линейной системы
a11x1 + a12x2 + … + a1nxn = b1,n+1
a21x1 + a22x2 + … + a2nxn = b2,n+1<shape id="_x0000_i1055" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image009.wmz» o:><img width=«12» height=«23» src=«dopb408104.zip» v:shapes="_x0000_i1055">
am1x1 + am2x2 + … + amnxn = bm.n+1
Здесь x1, x2, …, xn — неизвестные, которые надо определить. a11, a12, …, amn — коэффициенты системы — и b1, b2, … bm — свободные члены — предполагаются известными. Индексы коэффициентов (aij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.
Система (1) называется однородной, если все её свободные члены равны нулю (b1 = b2 = … = bm = 0), иначе — неоднородной.
Система (1) называется квадратной, если число m уравнений равно числу n неизвестных.
Решение системы (1) — совокупность n чисел c1, c2, …, cn, таких что подстановка каждого ci вместо xi в систему (1) обращает все ее уравнения в тождества.
Система (1) называется совместной, если она имеет хотя бы одно решение, и несовместной, если у нее нет ни одного решения.
Совместная система вида (1) может иметь одно или более решений.
Решения c1(1), c2(1), …, cn(1) и c1(2), c2(2), …, cn(2) совместной системы вида (1) называются различными, если нарушается хотя бы одно из равенств:
c1(1) = c1(2), c2(1) = c2(2), …, cn(1) = cn(2).
Совместная система вида (1) называется определенной, если она имеет единственное решение; если же у нее есть хотя бы два различных решения, то она называется неопределенной. Если уравнений больше, чем неизвестных, она называется переопределённой.
Решим следующую систему уравнений:
<imagedata src=«dopb408121.zip» o:><img border=«0» width=«222» height=«69» src=«dopb408121.zip» alt="\left\{\begin{array}{ccccccl}a &+& b &+& c &=& 0\\4a &+& 2b &+& c &=& 1\\9a &+& 3b &+& c &=& 3 \end{array}\right." v:shapes="_x0000_i1056">
Запишем её в виде матрицы 3Ч4, где последний столбец является свободным членом:
<imagedata src=«dopb408122.zip» o:><img border=«0» width=«132» height=«72» src=«dopb408122.zip» alt=" \begin{pmatrix} 1 & 1 & 1 & | & 0 \\ 4 & 2 & 1 & | & 1 \\ 9 & 3 & 1 & | & 3 \end{pmatrix}" v:shapes="_x0000_i1057">
Проведём следующие действия:
·                     К строке 2 добавим: -4 * Строку 1.
·                     К строке 3 добавим: -9 * Строку 1.
Получим:
<imagedata src=«dopb408123.zip» o:><img border=«0» width=«167» height=«72» src=«dopb408123.zip» alt=" \begin{pmatrix} 1 &\ 1 &\ 1 & | & 0 \\ 0 & -2 & -3 & | & 1 \\ 0 & -6 & -8 & | & 3 \end{pmatrix}" v:shapes="_x0000_i1058">
·                     К строке 3 добавим: -3 * Строку 2.
·                     Строку 2 делим на -2
<imagedata src=«dopb408124.zip» o:><img border=«0» width=«153» height=«72» src=«dopb408124.zip» alt=" \begin{pmatrix} 1 & 1 & 1 & | &\ 0 \\ 0 & 1 & {3 \over 2} & | & -{1 \over 2} \\ 0 & 0 & 1 & | &\ 0 \end{pmatrix}" v:shapes="_x0000_i1059">
·                     К строке 1 добавим: -1 * Строку 3.
·                     К строке 2 добавим: -3/2 * Строку 3.
<imagedata src=«dopb408125.zip» o:><img border=«0» width=«150» height=«72» src=«dopb408125.zip» alt=" \begin{pmatrix} 1 & 1 & 0 & | &\ 0 \\ 0 & 1 & 0 & | & -{1 \over 2} \\ 0 & 0 & 1 & | &\ 0 \end{pmatrix}" v:shapes="_x0000_i1060">
·                     К строке 1 добавим: -1 * Строку 2.
<imagedata src=«dopb408126.zip» o:><img border=«0» width=«150» height=«72» src=«dopb408126.zip» alt=" \begin{pmatrix} 1 & 0 & 0 & | &\ {1 \over 2} \\ 0 & 1 & 0 & | & -{1 \over 2} \\ 0 & 0 & 1 & | &\ 0 \end{pmatrix}" v:shapes="_x0000_i1061">
В правом столбце получаем решение:
<imagedata src=«166846.files/image048.png» o:><img border=«0» width=«176» height=«37» src=«dopb408127.zip» alt=«a = \frac{1}{2} \; ; \ b = -\frac{1}{2} \; ; \ c = 0» v:shapes="_x0000_i1062">.

3. Математическая обработка результатов опыта. Аппроксимация функций. Полином Лагранжа. Метод наименьших квадратов
<shape id="_x0000_i1063" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image009.wmz» o:><img border=«0» width=«12» height=«23» src=«dopb408104.zip» v:shapes="_x0000_i1063">В вычислительной математике нередки случаи, когда одну функцию приходится заменять другой, более простой и удобной для дальнейшей работы. Такую задачу называют аппроксимацией функций.
 Поводом для аппроксимации функции может послужить, в частности, табличный способ её задания. Предположим, что в результате некоторого эксперимента для конечного набора значений xi величины x из отрезка [a,b].
 a=x0 < x1 <…xi… < xn= b
получен набор значений yi величины y (табл. 4.1). Если допустить, что между x и y существует функциональная зависимость y = F(x), можно поставить вопрос о поиске аналитического представления функции F (очевидно, что в такой общей постановке эта задача решается неоднозначно). Точки x0, x1,… xn в этом случае называются узлами. Если расстояние h=xi+1- x1 является постоянным (т.е. независящим от i ), то сетка значений, представленная табл. 4.1, называется равномерной.
Таблица 4.1
 x
 x0
 x1
 x2
 …
 x1
 …
 xn
 F(x)
 Y0
 Y1
 Y2
 …
 Y1
 …
 yn
Повод для аппроксимации может возникнуть даже тогда, когда аналитическое выражение для некоторой функции y = F(x) имеется. однако оно оказывается мало пригодным для решения поставленной задачи, потому что операция, которую требуется осуществить над этой функцией, трудновыполнима. Элементарный пример — вычисление значения трансцендентной функции «вручную». Действительно, чтобы вычислить, например, In 3,2756, проще всего воспользоваться степенным разложением функции, т.е. заменить трансцендентную функцию степенной. При этом получится, разумеется, приближенное значение функции, но если мы умеем контролировать погрешность, то можно считать, что мы получили интересующий нас результат – хотя бы потому, что в реальности все равно приходится ограничиваться приближенным представлением значений логарифмической функции.
Другая ситуация, когда может потребоваться аппроксимация аналитически заданной функции, — вычисление определённых интегралов. Задача эта, как правило, весьма сложная, часто элементарными приемами невыполнимая. Как вычислить интеграл <shape id="_x0000_i1064" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image050.wmz» o:><img border=«0» width=«81» height=«49» src=«dopb408128.zip» v:shapes="_x0000_i1064"> Он, несомненно, существует, но по Формуле Ньютона – Лейбница вычислен быть практически не может, так как первообразная <shape id="_x0000_i1065" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image052.wmz» o:><img border=«0» width=«64» height=«41» src=«dopb408129.zip» v:shapes="_x0000_i1065"> не выражается в элементарных функциях (как и множество других первообразных от элементарных функций). Аппроксимация подынтегральной функции — один из возможных приемов (и важно отметить, что цель аппроксимации налагает отпечаток на ее способ).
Классический подход к численному решению подобных задач заключается в том, чтобы, опираясь на информацию о функции F, по некоторому алгоритму подобрать аппроксимирующую функцию G, в определенном смысле «близкую» к F.
Чаще всего задача аппроксимации решается с помощью многочленов. Вычисления значений многочлена легко автоматизировать, производная и интеграл от многочлена, в свою очередь, также являются многочленами. Наряду с многочленами для аппроксимации используют ряды Фурье, экспоненциальные и другие элементарные функции.
Для оценки «близости» функций выбирают тот или иной критерий согласия. Эти критерии основаны на использовании той или иной метрики, т.е. способа введения расстояния между функциями, принадлежащими тому или иному классу:
<shape id="_x0000_i1066" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image054.wmz» o:><img border=«0» width=«123» height=«21» src=«dopb408130.zip» v:shapes="_x0000_i1066"> (см. гл. 2).
Например, для функций, ограниченных на отрезке [a,b] расстояние может быть введено следующим образом:
<shape id="_x0000_i1067" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image056.wmz» o:><img border=«0» width=«16» height=«17» src=«dopb408131.zip» v:shapes="_x0000_i1067">(F(x),G(x))= <shape id="_x0000_i1068" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image058.wmz» o:><img border=«0» width=«139» height=«39» src=«dopb408132.zip» v:shapes="_x0000_i1068">;
для функций, непрерывных на отрезке [a,b], по формуле
<shape id="_x0000_i1069" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image060.wmz» o:><img border=«0» width=«120» height=«51» src=«dopb408133.zip» v:shapes="_x0000_i1069">
<shape id="_x0000_i1070" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image062.wmz» o:><img border=«0» width=«107» height=«51» src=«dopb408134.zip» v:shapes="_x0000_i1070">2dx
(а также многими другими способами).
Для функций, заданных таблично, достаточно распространенным критерием согласия является критерий Чебышева, который определяет расстояние <shape id="_x0000_i1071" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image064.wmz» o:><img border=«0» width=«16» height=«17» src=«dopb408131.zip» v:shapes="_x0000_i1071"> между аппроксимируемой и аппроксимирующей функциями как максимум величины отклонения между функциями в узлах сетки (см. табл. 4.1):
<shape id="_x0000_i1072" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image065.wmz» o:><img border=«0» width=«209» height=«60» src=«dopb408135.zip» v:shapes="_x0000_i1072"> (4.1)
Если <shape id="_x0000_i1073" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image067.wmz» o:><img border=«0» width=«16» height=«17» src=«dopb408131.zip» v:shapes="_x0000_i1073">=0, т.е. F(xi)=G(xi)=yi, то соответствующий способ аппроксимации называют интерполяцией, а процедуру вычисления значений F(x) с помощью G(x) в точках, не являющихся узлами сетки, — интерполированием.
С геометрической точки зрения график функции G(x) при интерполировании должен проходить через все точки A0(x0,y0), A1(x1,y1),…, An(xn,yn). Подчеркнем, что для значений x, не являющихся узловыми, значения функции G(x) ничем не регламентированы, и в принципе могут значительно отличаться от значений функций F(x)).
 Часто процедура аппроксимации связана с другим критерием согласия:
<shape id="_x0000_i1074" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image068.wmz» o:><img border=«0» width=«205» height=«45» src=«dopb408136.zip» v:shapes="_x0000_i1074"> (4.2)
Применяемый на его основе способ аппроксимации получил название метода наименьших квадратов.
Выбор критерия согласия позволяет строить методы, позволяющие однозначно определять параметры аппроксимирующей функции (если задан ее вид).<shape id="_x0000_i1075" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image009.wmz» o:><img border=«0» width=«12» height=«23» src=«dopb408104.zip» v:shapes="_x0000_i1075">
Полином Лагранжа.
Пусть Функция F(x) задана табл. 4.1. Построим многочлен Ln (x), степень которого не выше, чем n, и для которого выполнены условия интерполяции
Ln(x0)=y0, Ln(x1)=y1,…, Ln(xn)=yn. (4.6)
Будем искать Ln (x) в виде
Ln (x),=l0(x)+l1(x)+…+ln(x), (4.7)
где l1(x) – многочлен степени n, причем

l1(xл)=<shape id="_x0000_i1076" type="#_x0000_t75" o:ole=""><imagedata src=«166846.files/image070.wmz» o:><img border=«0» width=«97» height=«51» src=«dopb408137.zip» v:shapes="_x0000_i1076"> (4.8)
Очевидно, что требование (4.8) с учетом (4.7) вполне обеспечивает выполнение условий (4.6).
    продолжение
--PAGE_BREAK--