Метод Гаусса

Размещено на http://www.allbest.ru/

Министерство образования и науки, молодежи и спорта Украины

Харьковский национальный университет им. В. Н. Каразина

Факультет радиофизики, биомедицинской электроники и компьютерных систем

Доклад на тему:

Метод Гаусса для решения СЛАУ. Методы интегрирования Ньютона-Котеса

Подготовила

студентка гр. РР-31

Юшкова М.Н.

Преподаватель

Батраков Д.О.

Харьков-2015

Метод Гаусса для решения СЛАУ

Система уравнений - это условие, состоящее в одновременном выполнении нескольких уравнений относительно нескольких (или одной) переменных.

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

Необходимость решения систем линейных уравнений возникла у людей уже давно. Задачи, соответствующие современным задачам на составление и решение систем уравнений с несколькими неизвестными, встречаются еще в вавилонских и египетских рукописях II века до н.э., а также в трудах древнегреческих, индийских и китайских мудрецов. Данные задачи возникали при различных прикладных вопросах. Например, когда два землевладельца не могли поровну разделить территорию, так как она не всегда состояла из прямолинейных участков. Сначала стало ясно, что возможность сделать это появится, если разбить всю площадь на маленькие элементарные площадки, а после этого просуммировать их (то есть, взять интеграл под кривой в некоторых заданных пределах). Но данный метод не всегда оказывался достаточно точным, так как всё равно при делении всей площади на элементы, не удавалось сделать их одинаковыми, в силу криволинейности. Поэтому, были изобретены некоторые методы (можно сказать, уловки) для максимального увеличения точности деления. Одним из самых выгодных оказался метод парабол Симпсона. В нем криволинейные участки считают подобными параболам, описывающимся некоторыми формулами. Таким образом, человек, который делил площадь столкнулся с тем, что ему нужно решить некоторую систему, в данном случае, квадратных уравнений. Поэтому необходимо было придумать способ для того, чтобы сделать это легко и быстро. Одним из простейших и оказался метод Гаусса.

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

- нет необходимости предварительно исследовать систему уравнений на совместность (выяснять, есть у этой системы решения, или же их нет);

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

Для рассмотрения метода Гаусса нам понадобятся некоторые свойства и элементарные преобразования, которые часто используются для расчетов:

Строки матрицы можно переставлять местами.

Если в матрице есть одинаковые или пропорциональные строки, нужно удалить их все, кроме одной.

Нулевую строку следует удалять.

Любую строку матрицы можно разделить или умножить на любую константу (кроме нуля).

Обусловленность матрицы

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

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

Ответ на этот вопрос лежит в уточнении понятия «почти вырожденная». Если -- вырожденная матрица, то для некоторых решение не существует, тогда как для других оно будет неединственным. Таким образом, если почти вырождена, то можно ожидать, что малые изменения в и вызовут очень большие изменения в . С другой стороны, если -- единичная матрица, то и и -- один и тот же вектор. Следовательно, если близка к единичной матрице, то малые изменения в и должны влечь за собой соответственно малые изменения в .

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

Чтобы получить более точную и надежную меру близости к вырожденности, нам потребуется ввести понятие нормы вектора. Норма -- это число, которое измеряет общий уровень элементов вектора. Наиболее употребительной векторной нормой является евклидова длина

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

.

Эта норма обладает многими из аналитических свойств евклидовой длины, именно

, если ,

,

для всех скаляров ,

.

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

Максимум и минимум берутся по всем ненулевым векторам. Заметим, что если вырождена, то . Отношение называется числом обусловленности матрицы ,

Разберем методику решения СЛАУ методом Гаусса на конкретном примере.

Допустим, нам необходимо решить такую СЛАУ:

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

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

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

Работаем со столбцом №1

Умножим 2-ую строку на (k = -1 / 2 = -1/2) и добавим к 3-ой:

Умножим 1-ую строку на (k = -2 / 4 = -1/2) и добавим к 2-ой:

Работаем со столбцом №2

Умножим 2-ую строку на (k = 3 / 5/2 = 6/5) и добавим к 3-ой:

Получим единицы на главной диагонали. Для этого всю строку делим на соответствующий элемент главной диагонали:

Теперь исходную систему можно записать как:

= 5/4 - ( - 1/4 + 1/4)

= 1/5 - ( - 3/5)

= 3

Из 3-ой строки выражаем

=3

Из 2-ой строки выражаем

Из 1-ой строки выражаем

Решение получено.

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

Методы интегрирования Ньютона-Котеса

Основная идея большинства методов численного интегрирования состоит в замене подынтегральной функции на более простую, интеграл от которой легко вычисляется аналитически. Частным случаем является метод построения интегральных квадратурных формул для равномерных сеток, известный как формулы Ньютона-Котеса. Основной идеей метода является замена подынтегральной функции каким-либо интерполяционным многочленом. Далее будут рассмотрены методы прямоугольников, хорд и парабол.

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

Одним из самых простых методов является метод прямоугольников. Геометрически идея способа вычисления определённого интеграла по формуле прямоугольников состоит в том, что площадь криволинейной трапеции АВСD заменяется суммой площадей прямоугольников, одна сторона которых равна , а друга - .

Если суммировать площади прямоугольников, которые показывают площадь криволинейной трапеции с недостатком [Рисунок 1], то получим формулу:

Если с избытком [Рисунок 2], то

ньютон интегрирование уравнение матрица

Значения у0, у1,..., уn находят из равенств , к = 0, 1,..., n. Эти формулы называются формулами прямоугольников и дают приближённый результат. С увеличением n результат становится более точным.

Рис. 1

Рис. 2

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

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

Рис. 3

Метод парабол (метод Симпсона)

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

Рис. 4

Тогда формула для вычисления принимает сравнительно простой вид

При разбиении интервала на 2*N равных частей, получим формулу

Размещено на Allbest.ru