39. Прямые методы решения слау. Метод прогонки.

Одной из самых распространённых задач вычислительной математики является решение систем линейных алгебраических уравнений и ряда связанных с ним вопросов, таких как вычисление определителей, обращение матриц, отыскание их собственных значений. Этот круг вопросов называется задачами линейной алгебры. Система из n - линейных алгебраических уравнений с n - неизвестными имеет вид:

где аij, bi-известные величины, Хi- неизвестные.

Система (1) в сокращённом виде:

Система (1) в матричном виде:

Известно, что система (1) имеет единственное решение, если определитель матрицы:

Δ=det A не равен нулю.

В противном случае система (1) не имеет решения, либо имеет бесконечное множество решений. Будем считать, что Δ = detA не равен нулю.

Для решения системы (1) имеются две группы методов: прямые и итерационные методы.

Прямыми называют такие методы, которые используют конечные соотношения (формулы) для выполнения заранее известного числа операций. При этом, если исходные данные точны, то результат будет точным, поэтому прямые методы называют точными методами. Но исходные данные обычно не точны и при решении задачи прямыми методами происходит накопление погрешностей. Чем больше число уравнений, тем больше погрешностей, поэтому прямые методы используют, если n<200.

К прямым методам относятся, формулы Крамера, метод Гауса, метод Жордана и метод прогонки.

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

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

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

x2= u2х3+ v1, полученное выражение х2 в 3 -е уравнение, чтобы исключить х2 и т.д., то на i-ом шаге исключения получим формулу:

Прямые методы. Формула Крамера

Ах+В

Хi=Δ\Δi , i=1, n

Δ- определитель матрицы. Δi - определитель матрицы, получаемой заменой i--го столбца матрицы столбцом из свободных членов:

2х+3y=7 -x+4y=3 Формула Крамера при небольших n требует приблизительно nn!- операций.

Наиболее распространённым среди прямых методов является метод исключения Гаусcа. Метод приводит к значительно меньшему объёму вычислений, чем формула Крамера. Метод Гаусcа состоит из прямого и обратного хода. Прямой ход - это приведение матрицы системы к верхнему треугольному виду, иначе говоря, система преобразуется т.о., чтобы исключить х1 из всех уравнений кроме 1-го, х2- из всех кроме 1-го и 2-го. Для этого делим 1-ое уравнение на а11, умножаем на аi1 и вычитаем из i-го уравнения системы.i=2,3…n.

В результате, из всех кроме 1-го уравнения исключается х1, затем с помощью 2-го х2 и т.д.

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

Из n-го уравнения находим хn: полученное значение в xn подставляем в (n-1) , откуда находим x(n-2) и т.д. Метод Гаусса требует выполнения 2/3n^3 - операций.

40. Итерационные методы решения СЛАУ.

41. Методы простой итерации и Зейделя для решения систем нелинейных уравнений.

42. Метод Ньютона для решения систем нелинейных уравнений.

43. Аппроксимация функций. Постановка задачи и способы ее решения.

44. Интерполяцинные многочлены Лагранжа.

45. Интерполяционные многочлены Ньютона.

46. Обработка результатов эксперимента. Метод наименьших квадратов.

47. Формулы численного интегрирования. Формулы прямоугольников и трапеций.

Численное интегрирование (историческое название: (численная) квадратура) — вычисление значения определённого интеграла(как правило, приближённое). Под численным интегрированием понимают набор численных методов отыскания значения определённого интеграла.

Численное интегрирование применяется, когда:1. Сама подынтегральная функция не задана аналитически. Например, она представлена в виде таблицы (массива) значений в узлах некоторой расчётной сетки. 2. Аналитическое представление подынтегральной функции известно, но её первообразная не выражается через аналитические функции. Например, f(x) = exp( − x²).

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

Формулы прямоугольников Пусть требуется определить значение интеграла функции на отрезке  . Этот отрезок делится точками  на   равных отрезков длиной   Обозначим через   значение функции   в точках   Далее составляем суммы   Каждая из сумм — интегральная сумма для   на   и поэтому приближённо выражает интеграл

Если заданная функция — положительная и возрастающая, то эта формула выражает площадь ступенчатой фигуры, составленной из «входящих» прямоугольников, также называемая формулой левых прямоугольников, а формула

выражает площадь ступенчатой фигуры, состоящей из «выходящих» прямоугольников, также называемая формулой правых прямоугольников. Чем меньше длина отрезков, на которые делится отрезок  , тем точнее значение, вычисляемое по этой формуле, искомого интеграла.

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

где  Учитывая априорно бо́льшую точность последней формулы при том же объеме и характере вычислений её называют формулой прямоугольников

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

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

Площадь трапеции на каждом отрезке:

Погрешность аппроксимации на каждом отрезке:

 где  Полная формула трапеций в случае деления всего промежутка интегрирования на отрезки одинаковой длины h:

 где 

Погрешность формулы трапеций:  где