ВМ (Ответы на экзаменационные вопросы в виде шпаргалки), страница 2

Метод Стеффенса. В формулу метода Ньютона сделаем замену f  (x )  f(z ⁿ ) - f(x ⁿ )/ z ⁿ - x ⁿ при условии z ⁿ  x ⁿ и следует из определения производной f  (x ) = lim z x f(z)-f(x)/z-x.

Заменив z ⁿ = x ⁿ + f(x ⁿ ), x ⁽ⁿ⁺¹⁾ = x ⁿ - f²(x ⁿ )/ f(x ⁿ + f(x ⁿ ))- f(x ⁿ ), n  0.

Г еометрическая иллюстрация.

Приближение x ⁿ получается как абсцисса т. пересечения с 0 x секущей, проходящей через т. М ⁿ и N ⁿ c координатами (x ⁿ , f(x ⁿ)) и (z ⁿ , f(z ⁿ )).Значение z ⁿ соответствует абсциссе т. пересечения с осью 0x прямой y = f(x ⁿ ) – (x - x ⁿ ), проходящей через т. Мⁿ и параллельной прямой y = - x.

ВОПРОС №7. Методы решения СЛАУ. Прямые и итерационные методы. Условие сходимости итерационных методов.

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

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

Вторую группу составляют приближенные методы (итерационные) решения СЛАУ.

Метод Гаусса Предназначен для решения СЛАУ вида:

или Ах=в

, ,

Предположим, что матрица А - невырожденная, т.е. det А не равно 0. В этом случае решение системы существует и оно единственно, а рассматриваемая задача корректна.

Вычисления с помощью метода Гаусса. Состоят из двух шагов, называемых прямым и обратным ходом. Прямой ход метода Гаусса заключается в последовательном исключении неизвестных из системы с верхней треугольной матрицей. Вычисления значений неизвестных производят на этапе обратного хода. Рассмотрим простейший вариант метода Гаусса, называемый схемой единственного деления. Прямой ход состоит из (n-1) шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного x₁ из уравнений с номерами i = 2,3,...,n. Предположим, что коэффициент a₁₁  0 (главный элемент первого шага)

Вычислим величины _i1=a_i1 /a₁₁(i=2,3,...,n), называемые множителями 1-го шага. Вычтем из второго, третьего и ... до n-го уравнений системы (1) первое уравнение, умноженное соответственно на  ₂₁,₃₁,..., _n1.Это позволит обратить в нуль коэффициенты при х₁ во всех уравнениях , кроме первого. В результате получим эквивалентную систему.

в которой a_ij⁽¹⁾=a_ij-_i1 a_ij , b_i⁽¹⁾=b_i-_i1 b₁.

2-й шаг. На этом шаге производится исключение х₂ из уравнений с номерами i = 3, 4, . . . , n.

Вычислим _i2=a_i2⁽¹⁾/ a₂₂⁽¹⁾ относительно главного элемента 2-го шага, после чего произведем те же действия по исключению элементов а_i2 из 3-й n . . . строк.

Аналогично проводятся остальные шаги.

k-й шаг. Предположим, что главный элемент k-го шага a_kk^(k-1)0, вычислим множители k-го шага
_ik= a_ik^(k-1)/a_kk^(k-1) , (i=k+1,...,n) и вычтем последовательно из (k + 1)-го , . . . , n-го уравнений полученной на предыдущем шаге системы k-е уравнение, умноженные соответственно на  _k+1,_k+2,..., _nk.

После (n -1) - го шага исключения получим систему уравнений

(2)

Получается матрица А^(n-1), которая является верхней треугольной. На этом вычисления прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы (2) вычислим х_n. Подставляя полученное значение в предпоследнее уравнение, вычислим значение х_n-1. Таким образом, можно вычислить значения всех неизвестных. Вычисления здесь проводятся по формулам:

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

Для того чтобы применить метод простой итерации к решению системы ЛАУ

Aх = b (3)

С квадратной невырожденной матрицей А, необходимо преобразовать эту систему к виду

х = Вх + с, (4)

где В - квадратная матрица с элементом b_ij (i,j=1.n), с - вектор столбец с элементами c_i (i=1,n).

Зададим некоторое начальное приближение x⁽⁰⁾=(x₁⁽⁰⁾,x₂⁽⁰⁾,..., x_n⁽⁰⁾)^T. Подставив его в правую часть системы (4), находим первое приближение x₍₁₎= Bx₍₀₎+c и так далее.

Сходимость метода простой итерации.

||B||<1. В этом случае существует и единственное решение системы (3) x. При этом метод итерации сходится при произвольном начальном приближении x⁽⁰⁾.

||B|| - норма матрицы.

Евклидова норма матрицы, имеет вид:

Критерий окончания итерационного процесса.

||x⁽ⁿ⁾-x^(n-1)|| < 

Метод Зейделя.

Пусть система (3) приведена к виду:

С коэффициентами, вычисленными по формулам:

в_ij = - a_ij / a_ii , c_ij = в_i / a_ii (i,j = 1,n , j i)

Метод Зейделя представляет собой модификацию метода простых итераций. Идея метода состоит в том, что при вычислении на (k+1)-ом шаге приближения к неизвестному х_i при i>1, используется уже найденное (k+1)-е приближение x ₁ , x ₂, . . . , x _i-1

Таким образом матрица В разбивается на две треугольные матрицы: верхнюю и нижнюю.

Расчетная формула принимает вид:

x ^k+1 =B₁ x ^k+1 + x ^k + C

или

Условия сходимости и критерий окончания итерационного процесса те же.

ВОПРОС №8. Метод простой итерации для решения СНУ. Теорема о сходимости методов.

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

f₁ (x₁, x₂, . . . , x_n) =0,

f₂ (x₁, x₂, . . . , x_n) =0,

..........

f_n (x₁, x₂, . . . , x_n) =0,

Найти точное решение системы (1), то есть вектор x = (x₁, x₂, . . . , x_n)^T удовлетворяющий уравнениям (1), практически невозможно, так как в описанном случае исключается использование прямых методов. Реальным путем решения системы (1) является использование итерационных методов для получения приближенного решения x^* = (x₁^*, x₂^* , . . . , x_n^*) удовлетворяющего при заданном  > 0 неравенству ||x^* - x|| < .

Для удобства будем использовать сокращенную векторную форму записи систем: вектор неизвестных x = (x₁, x₂, . . . , x_n)^T и векторную функцию f = (f₁, f₂, . . . , f_n)^T.

В этих обозначениях система (1) примет вид:

f (x) = 0. (2)

Метод релаксации.

Имеем систему: Преобразуем ее к виду: Зададим начальное приближение: x⁽⁰⁾=(x₁⁽⁰⁾, x₂⁽⁰⁾,...,x_n⁽⁰⁾)

и подставим в полученную систему.
Получаем невязки (отклонения).

Если одной из неизвестных x_s⁽⁰⁾ задать приращение  x_s⁽⁰⁾, то соответствующая невязка уменьшится на эту величину, а все остальные невязки R_i⁽⁰⁾(iS) увеличатся на величину b_is x_s⁽⁰⁾.то есть, чтобы обратить очередную невязку R_s⁽¹⁾ в нуль, необходимо величине x_s⁽⁰⁾ дать приращение  x_s⁽⁰⁾= R_s⁽⁰⁾ и получим R_s⁽¹⁾=0 и R_i⁽¹⁾= R_i⁽⁰⁾ + b_is x_s⁽⁰⁾.

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

Будем считать функции f_i(x), входящие в систему (1) непрерывно дифференцируемыми в некоторой окресности решения x¯. Введем для системы функций f₁,f₂,...,f_n матрицу Якоби

( 3)

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

Преобразуем систему (1) к эквивалентному виду:

(4)

Зададим начальное приближение x⁽⁰⁾= (x1⁽⁰⁾,x2⁽⁰⁾,...,xn⁽⁰⁾. Подставляя его в правую часть системы (4) получим первое приближение к решению. Повторяя этот процесс решения системы (1). Очередное приближение x^(k+1)вычисляется по формулам

Е сли ввести в рассмотрение векторную функцию  =(₁,₂, ...,_n), то итерационный процесс можно записать кратко

x^(k+1)=(x^(k)). (5)

По аналогии с МПИ для решения одного нелинейного уравнения рассмотрим условия работоспособности МПИ для СНУ.

Сходимость метода.

Пусть '(x) - матрица Якоби, отвечающая вектор - функции (x).

Теорема. Пусть в некоторой  - окрестности решения x¯ функции _i(x) (i=1,n¯) дифференцируемы и выполнено неравенство

||'(x)||g, где 0g<1 (const).

Тогда независимо от выбора начального приближения x⁽⁰⁾ из указанной -окрестности корня итерационная последовательность не выходит из этой окрестности, метод сходится со скоростью геометрической прогрессии и справедлива следующая оценка погрешности:

На практике часто используется следующая оценка окончания итерационного процесса:

||x⁽ⁿ⁾-x^(n-1)|| ₁

Метод Ньютона для решения СНУ.

Обобщим метод Ньютона для решения одного НУ на решение системы НУ (1).

Предположим, что исходя из начального приближения x⁽⁰⁾ к решению x¯ построены приближения x⁽¹⁾, x⁽²⁾,...,x⁽ⁿ⁾.Заменим в системе (1) каждую функцию f_i (i=1,n¯)линейной частью ее разложения по формуле Тейлора в точке x⁽ⁿ⁾: