Квадратурная формула гаусса

Квадратурная формула Гаусса на первый взгляд похожа на формулу Чебышева

квадратурная формула гаусса - student2.ru . (2.18)

Только Гаусс для своей формулы предложил другое условие: Квадратурная формула (2.18) точна для всех полиномов максимально возможной степени M.

В формуле (2.18) насчитывается квадратурная формула гаусса - student2.ru неизвестных - квадратурная формула гаусса - student2.ru и квадратурная формула гаусса - student2.ru . Для их единственного определения нам необходимо иметь квадратурная формула гаусса - student2.ru уравнений.

Если подставить полиномы квадратурная формула гаусса - student2.ru в формулу (2.18), мы получим недостающие квадратурная формула гаусса - student2.ru уравнений:

квадратурная формула гаусса - student2.ru . (2.19)

Система (2.19) является нелинейной, ее можно решить с помощью полиномов Лежандра. Решение данной системы - коэффициенты квадратурная формула гаусса - student2.ru и квадратурная формула гаусса - student2.ru даны в таблице:

n k tk Ak
1; 2 квадратурная формула гаусса - student2.ru 0.57735027
1; 3 квадратурная формула гаусса - student2.ru 0.77459667 0.55555556 0.88888889
1; 4 2; 3 квадратурная формула гаусса - student2.ru 0.86113631 квадратурная формула гаусса - student2.ru 0.33998104 0.34785484 0.65214516
1; 5 2; 4 квадратурная формула гаусса - student2.ru 0.90617985 квадратурная формула гаусса - student2.ru 0.53846931 0.23692688 0.47862868 0.56888889
1; 6 2; 5 3; 4 квадратурная формула гаусса - student2.ru 0.93246951 квадратурная формула гаусса - student2.ru 0.66120939 квадратурная формула гаусса - student2.ru 0.23861919 0.17132450 0.36076158 0.46791394
1; 7 2; 6 3; 5 квадратурная формула гаусса - student2.ru 0.94910791 квадратурная формула гаусса - student2.ru 0.74153119 квадратурная формула гаусса - student2.ru 0.40584515 0.12948496 0.27970540 0.38183006 0.41795918
1; 8 2; 7 3; 6 4; 5 квадратурная формула гаусса - student2.ru 0.96028986 квадратурная формула гаусса - student2.ru 0.79666648 квадратурная формула гаусса - student2.ru 0.52553242 квадратурная формула гаусса - student2.ru 0.18343464 0.10122854 0.22238104 0.31370664 0.36268378

Для вычисления общего интеграла

квадратурная формула гаусса - student2.ru

применяют замену переменных

квадратурная формула гаусса - student2.ru .

В результате квадратурная формула Гаусса имеет вид:

квадратурная формула гаусса - student2.ru (2.20)

где

квадратурная формула гаусса - student2.ru . (2.21)

Т.о. формула Гаусса является более точной по сравнению с формулой Чебышева и позволяет вычислять точное значение интеграла для полиномов степени квадратурная формула гаусса - student2.ru (т.е. 15 степени по сравнению с 9 степенью формулы Чебышева).

Методы решения СЛАУ

Постановка задачи

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

квадратурная формула гаусса - student2.ru . (3.1)

В дальнейшем будем записывать ее в виде

квадратурная формула гаусса - student2.ru , где квадратурная формула гаусса - student2.ru , квадратурная формула гаусса - student2.ru , квадратурная формула гаусса - student2.ru . (3.2)

Методы решения систем линейных алгебраических уравнений (СЛАУ) делятся на две группы: точные и итерационные.

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

Итерационные методы состоят в том, что решение системы (3.1) находится как предел при квадратурная формула гаусса - student2.ru последовательных приближений квадратурная формула гаусса - student2.ru , где квадратурная формула гаусса - student2.ru - номер итерации. Как правило, за конечное число итераций предел не достигается. Обычно задается некоторое число квадратурная формула гаусса - student2.ru (погрешность) и вычисления проводятся до тех пор, пока не будет выполнена оценка квадратурная формула гаусса - student2.ru .

Выбор метода из списка существующих производится в соответствии с

· Размерностью задачи. Прямые методы используют для задач при квадратурная формула гаусса - student2.ru , при больших квадратурная формула гаусса - student2.ru применяют итерационные методы.

· Характером матрицы. Существует несколько типов матриц, таких как симметричные матрицы, положительно определенные матрицы, треугольные матрицы и т.д. В зависимости от типа матрицы задачи используют различные численные методы.

· Объемом памяти и быстродействием ЭВМ. На ЭВМ с большим объемом памяти используют методы, которые требуют много памяти, но и решение задачи получается быстрым. Для ЭВМ с высоким быстродействием применяют методы с большим количеством вычислений, но с меньшими требованиями к размеру оперативной памяти.

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

Сопоставление между собой прямых методов проводится обычно по числу арифметических действий, необходимых для получения решения. При прочих равных условиях предпочтение отдается методу с меньшим числом операций. Например, для метода Гаусса требуется порядка квадратурная формула гаусса - student2.ru действий, а для метода Крамера порядка квадратурная формула гаусса - student2.ru операций.

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

Ниже будут представлены прямые методы - метод Крамера, варианты метода Гаусса и схема Халецкого, и итерационные методы - метод Якоби, Зейделя, верхней релаксации и метод итераций.

Метод Крамера

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

квадратурная формула гаусса - student2.ru , квадратурная формула гаусса - student2.ru ,

где матрица квадратурная формула гаусса - student2.ru получается из матрицы квадратурная формула гаусса - student2.ru заменой столбца i на столбец свободных членов F.

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

Метод Гаусса

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

Метод Гаусса выполняется в два этапа:

Þ Прямой ход. Система уравнений приводится к треугольному виду.

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

Итак, решение системы уравнений (3.1) по схеме единственного деления заключается в следующем:

Предположим, что коэффициент квадратурная формула гаусса - student2.ru . Разделим коэффициенты первого уравнения системы (3.1) на квадратурная формула гаусса - student2.ru . Первое уравнение примет вид:

квадратурная формула гаусса - student2.ru , (3.3)

где

квадратурная формула гаусса - student2.ru для квадратурная формула гаусса - student2.ru и квадратурная формула гаусса - student2.ru .

Используя уравнение (3.3), можно исключить из системы (3.1) неизвестную квадратурная формула гаусса - student2.ru (везде, кроме первого уравнения). Для этого вычтем из второго уравнения системы уравнение (3.3), умноженное на квадратурная формула гаусса - student2.ru . Далее, из третьего уравнения вычтем уравнение (3.3), умноженное на квадратурная формула гаусса - student2.ru и т.д. В результате получим следующую систему

квадратурная формула гаусса - student2.ru , (3.4)

где коэффициенты квадратурная формула гаусса - student2.ru и квадратурная формула гаусса - student2.ru для квадратурная формула гаусса - student2.ru вычисляются по формулам

квадратурная формула гаусса - student2.ru и квадратурная формула гаусса - student2.ru .

Предполагаем, что коэффициент квадратурная формула гаусса - student2.ru и аналогичным способом исключаем из системы (3.4) неизвестную квадратурная формула гаусса - student2.ru (кроме первого и второго уравнения). Далее избавляемся от неизвестного квадратурная формула гаусса - student2.ru и т.д. В результате получаем следующую систему уравнений

квадратурная формула гаусса - student2.ru , (3.5)

Итак, в результате выполнения первого этапа метода Гаусса - прямого хода - от системы уравнений (3.1) переходим к эквивалентной ей системе уравнений (3.5) с треугольной матрицей. Как известно, решение системы уравнений с треугольной матрицей является достаточно простой операцией и выполняется по следующим формулам:

квадратурная формула гаусса - student2.ru ,

квадратурная формула гаусса - student2.ru и т.д.

Общая формула имеет вид:

квадратурная формула гаусса - student2.ru , (3.6)

где квадратурная формула гаусса - student2.ru .

Примечание. При квадратурная формула гаусса - student2.ru имеем квадратурная формула гаусса - student2.ru и квадратурная формула гаусса - student2.ru .

Коэффициенты, стоящие на главной диагонали системы (3.5) - квадратурная формула гаусса - student2.ru , квадратурная формула гаусса - student2.ru , ..., квадратурная формула гаусса - student2.ru , - называются главными (или ведущими) элементами. Систему уравнений можно решить методом Гаусса, если все ее главные элементы отличны от нуля. В противном случае система единственного решения не имеет. Поэтому при исключении неизвестных на первом этапе рекомендуется проверить главный элемент текущего уравнения на равенство нулю.

Метод Гаусса является точным методом и теоретически дает точное решение системы уравнений (3.1). На практике методом Гаусса можно получить только приближенное решение. При вычислениях на компьютерах возникают ошибки округления, которые понижают точность вычислений.

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

квадратурная формула гаусса - student2.ru .

Исключили неизвестную квадратурная формула гаусса - student2.ru и получили систему

квадратурная формула гаусса - student2.ru .

Исключаем неизвестную квадратурная формула гаусса - student2.ru :

квадратурная формула гаусса - student2.ru

Прямой ход закончился. Выполняем второй этап и получаем следующее решение:

квадратурная формула гаусса - student2.ru ,

в то время как точное решение имеет вид:

квадратурная формула гаусса - student2.ru .

На примере видно, что небольшая погрешность для квадратурная формула гаусса - student2.ru , равная 0.0008, стремительно увеличивается для квадратурная формула гаусса - student2.ru до 0.4286 и достигает максимума для квадратурная формула гаусса - student2.ru (1.9021).

Итак, приближенное решение квадратурная формула гаусса - student2.ru почти в три раза больше точного решения квадратурная формула гаусса - student2.ru . Данное возмущение связано со вторым уравнением. Главный элемент второго уравнения равен 0.0007. В соответствии с формулой (3.6) погрешность решения квадратурная формула гаусса - student2.ru увеличилась в квадратурная формула гаусса - student2.ru раз.

Если бы вычисления проводились без ошибок округления, то решение было бы точным. Но к сожалению, все расчеты с вещественными числами выполняются только приближенно. В зависимости от типа вещественного числа (Real, Single, Extended и т.д.) точными являются 10-20 знаков.

Вычислительную погрешность можно существенно уменьшить. Причина резкого роста погрешности заключена в малости ведущего элемента. Чтобы повысить точность метода, необходимо выбрать другой ведущий элемент. Существует несколько вариантов выбора главного элемента - по строкам, по столбцам и по матрице. Пусть необходимо исключить неизвестную квадратурная формула гаусса - student2.ru , т.е. работаем с i-тым уравнением. Выберем максимальный по модулю коэффициент в i-том столбце, из числа стоящих на главной диагонали и ниже. Пусть это будет коэффициент из j-того уравнения. Поменяем местами уравнения № i и j. Продолжим исключение неизвестных. Описанный алгоритм и есть метод Гаусса с выбором главного элемента по столбцам. Если максимальный по модулю элемент будем искать в i-той строке, то получим метод Гаусса с выбором главного элемента по строкам. При выборе главного элемента в матрице поиск осуществляется в матрице коэффициентов - в строках от i до n и столбцах от i от n.

В вышеописанном примере для исключения неизвестного квадратурная формула гаусса - student2.ru применим выбор главного элемента по столбцам. Ведущий элемент будет равен -16.895. В результате получим приближенное решение

квадратурная формула гаусса - student2.ru .

Следовательно, несмотря на ошибки округления, погрешность решения не превысила 0.0003

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

{Перебираем номера неизвестных k от первого до}

{предпоследнего. Будем исключать неизвестную x[k]}

For k:=1 to N-1 do

begin

{Если главный элемент равен нулю, даем}

{сообщение и завершаем работу программы}

If Abs(A[k,k])<0.001 then

begin

Writeln(’Главный элемент равен нулю.’);

Writeln(’Данную схему применять нельзя.’);

Halt(1);

end;

{Перебираем уравнения от k+1 до последнего}

For i:=k+1 to N do

begin

{Перебираем коэффициенты уравнения}

For j:=k+1 to N do

{и вычисляем их новые значения}

A[i,j]:=A[i,j]-A[i,k]*A[k,j]/A[k,k];

{Вычисляем значение коэфф. правой части}

F[i]:=F[i]-A[i,k]*F[k]/A[k,k];

end;

end;

Для получения решения системы уравнений применяется формула (3.6). Алгоритм вкратце выглядит следующим образом. Осуществляют перебор номеров i от n do 1. Вычисляют выражение, стоящее в скобках, обращая внимание на правильность суммирования, и значение дроби.

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

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

{В массиве Por хранится информация о }

{местоположении элементов решения}

Var Por:Array[1..N] of Integer;

...

{После ввода коэфф. системы, задаем массив Por}

For i:=1 to N do Por[i]:=i;

...

{Пусть на I-том шаге исключения главный}

{элемент находится в j-том столбце.}

{Необходимо поменять местами коэффициенты }

{i и j столбца. Изменяем соответственно данные}

{в массиве Por. Для этого используем}

{переменную Vsp типа Integer}

Vsp:=Por[i]; Por[i]:=Por[j]; por[j]:=Vsp;

...

{Решили систему уравнений, далее требуется}

{восстановить решение. Полученное решение было}

{записано в массив X.}

{Восстановленное решение запишем в массив Xnew}

For i:=1 to N do

Xnew[i]:=X[Por[i]];

Наши рекомендации