23 Метод Ньютона.

Пусть снова задано уравнение f(x)=0. Запишем его в виде , где и . Пустьх_к – некоторое приближение к корню х*. Для ускорения сходимости итераций желательно, чтобы был как можно меньше. Положим, то есть

Отсюда находим, что . Подставляя в исходное уравнение, получаем рекуррентную формулу:. Это и есть итерационная процедура Ньютона.

24.Численные методы линейной алгебры.

К численным методам линейной алгебры относятся: численные методы решения систем алгебраических уравнений (ЛАУ), обращение матриц, вычисление определителя матрицы, вычисление собственных значений и собственных векторов матриц. Численные методы решения систем ЛАУ можно разбить на две группы: прямые методы (метод исключения Гаусса и его модификации) и так называемые итерационные методы. Метод Гаусса подробно рассматривается в курсе линейной алгебры, где, в частности показывается, что число арифметических действий, затрачиваемых на приведение системы к треугольному виду пропорционально n³. При вычислении определителя методом Гаусса затрачивается арифметических действий. Несмотря на очевидные преимущества прямых методов (конечность действий), их применение не всегда возможно. Если матрицаA линейной системы плохо обусловлена, то вследствие неизбежных ошибок округления на ЭВМ, полученное приближенное решение системы может оказаться сколь угодно далеким от точного решения. Чтобы разобраться в этом вопросе, нам понадобится понятие нормы матрицы, спектра матрицы и обсудить некоторые дополнительные свойства матриц, связанные с этими понятиями.

25.

Нормы матриц. Спектральные свойства матриц. Пусть , ОбозначимM_n- множество квадратных матриц. Пусть каждой матрицепоставлено в соответствие число.Это число называетсянормой матрицыA, если выполняются следующие аксиомы:

1. . 2.. 3.(неравенство треугольника).

4. (кольцевое свойство).

Определение.Норма называетсямультипликативной, если выполняются все четыре аксиомы, и аддитивной, если выполняются первые три аксиомы.

Следствие. Если норма матрицы A – мультипликативна, то согласно свойству 4: . Пусть . Определим норму матрицы следующим образом:

. (1) Таким образом, определенная норма матрицы называется подчиненной векторной норме .

Определение. Если матричная норма удовлетворяет условию , (2) то такая норма называется согласованной с нормой вектора.

Следствие 1.Любая подчиненная норма является также и согласованной (обратное вообще говоря, неверно).

Действительно, из (1) в силу определения супремума: , Тот факт, что обратное неверно, подтверждается конкретными примерами матричных норм, с которыми мы познакомимся далее.

Следствие 2. Пусть A=E и норма матрицы – подчиненная векторной норме. Тогда, поскольку Ex=x, то и из (1) немедленно следует что Полученное условие можно считать необходимым условием подчиненной нормы. Определим некоторые наиболее употребительные на практике матричные нормы.

- евклидова норма (норма Фробениуса: norm(a, ‘fro’)- в MATLAB),

- “столбцовая” норма (norm(a, 1)),

- “строчная” норма (norm(a, inf)),

- “спектральная” норма (norm(a)=norm(a, 2)), где - так называемыесингулярные числа матрицы А.

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

Определение 1. Число (вообще говоря, комплексное) называется собственным значением матрицыА, соответствующим собственному вектору x, если выполняется условие: . (3)

Определение 2. Множество всех собственных чисел матрицы А , записанных с учетом их кратности, называетсяспектром матрицы А и обозначается S(A).

Определение 3. Спектральным радиусом квадратной матрицыА называется максимальный из модулей ее собственных значений. Заметим, что система (3) эквивалентна следующей однородной системе уравнений: . (4)

Как известно из курса линейной алгебры, система (4) имеет нетривиальные решения тогда и только тогда, когда. (5) Уравнение (5)- алгебраическое уравнение n-ой степени относительно .

Все его корни – собственные числа матрицы А. Имеет место следующая

Теорема 1. Для любой квадратной матрицы и любой согласованной матричной нормы имеет место неравенство:

Пусть - произвольное собственное значение матрицыA, и - соответствующий собственный вектор . Оценим по нормеОпределение 4. Сингулярным числом матрицыА называется собственное значение матрицы .

Определение 5. Матрица А называется положительно (неотрицательно) определенной (пишут: или), если соответствующая квадратичная форма .

Простейшие следствия из определений.

Следствие 1. Критерий Сильвестра: все ведущие угловые миноры матрицыА положительны.

Следствие 2. , причем. следует из критерия Сильвестра

Следствие 3. все собственные значения. Пусть- собственное значение, соответствующее собственному векторуx.

По условию результат.

Следствие 4. Пусть А – вещественная матрица матрицаИмеем:{по свойству скалярного произведения}

Следствие 5. Сингулярные числа вещественной матрицы А – неотрицательныСледует из С3 и С4.

Следствие 6. Пусть А – вещественная матрица .

Имеем:

Следствие 7. Если А – невырожденная матрица собственные значения матрицА и A^-1 взаимообратны.

Пустьрезультат.

Обусловленность матриц и систем уравнений. Пусть дана система ЛАУ с невырожденной матрицей А : Ax=b, (6) и пусть вектор правой части b вычисляется с ошибкой . Заменим правую часть “возмущенным” значением , тогда решение приобретет ошибкуи система примет вид:

. (7) Оценим относительную ошибку решения в зависимости от относительной

величины возмущения правой части . Из (6) и (7) следует:или

{согласованность матриц}(8) С другой стороны, из (6) следуетподставим в (8).

(9)

Определение 6. Число называетсячислом обусловленности матрицы А. Таким образом, из (9) следует, что максимальная относительная ошибка решения пропорциональна числу обусловленности матрицы А: .

Если (система уравненийплохо обусловлена), то небольшие погрешности вычисления правой части (небольшие “возмущения”) могут приводить к весьма большим отклонениям от точного решения.

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

26

Итерационные методы решения систем ЛАУ.Рассмотрим вначале систему ЛАУ вида x=Tx+d,,T- матрица(10) Назовем эту систему системой “второго рода”, в отличии от вида системы (1) – системы “первого рода”. Систему второго рода (10) естественно пытаться решать итерационным методом

, k=0,1,….. (11) В этом методе используются лишь операции сложения и умножения, и не используется операция деления – наиболее опасная для накопления ошибок. Очевидно, что оператор Т - линейный и отображает Rⁿ в себя. Тогда согласно У2 из лекции 10, если для какой-либо из матричных нормвыполняются условия теоремы 1существует единственная неподвижная точкаx^* оператора Т, удовлетворяющая системе x*=Tx*+d, (12) причем процедура (11) сходится к точке x^* со скоростью геометрической прогрессии. Действительно, из (11) и (12) x^k+1-x^*=T(x^k-x^*)={продолжая рекурсию}=…=T^k(x⁰-x^*) Оценивая по норме, получаем: {согласованность+мультипликативность матричной нормы}прирезультат: сходимость с линейной скоростью.