17. Метод Гивенса

При использовании метода Гивенса угол ротации выбирается таким, чтобы обнулить элемент, находящийся не на одном из четырех углов, т.е. не app, apq или aqq. Конкретно, матрица P23 используется для обнуления a31 (и по симметрии a13). Затем P24 используется для обнуления a41. В целом, используется последовательность

P23, P24, ..., P2n; P34, ..., P3n; ...; Pn-1,n

для обнуления ak,j-1 с помощью Pjk. Метод работает, поскольку такие элементы, как a'rp и a'rq при r!=p и r!=q суть линейные комбинации старых значений arp и arq. Таким образом, если arp и arq уже нулевые, то они таковыми останутся и после ротации. Очевидно, требуется порядка n2/2 ротаций, а число умножений в алгоритме будет порядка 4n3/3, не считая тех, которые требуются для преобразования произведения трансформирующих матриц, необходимого для вычисления собственных векторов.

Метод Хаусхолдера, который будет описан ниже, является таким же устойчивым, как и редукция Гивенса, но требует в 2 раза меньше операций, таким образом, метод Гивенса обычно не используется. Однако недавние исследования [6] показали, что редукция Гивенса может быть переформулирована так, чтобы повысить ее эффективность примерно в 2 раза, а также избежать вычисления квадратных корней. В результате этого "быстрый метод Гивенса" становится конкурентоспособным с методом Хаусхолдера. С другой стороны, быстрый метод должен отслеживать возможности переполнения, и переменные должны быть периодически перемасштабируемы при его использовании. Это обстоятельство говорит о том, что метод Хаусхолдера все же предпочтительнее.

19.Липшица Условие

Липшица условие, ограничение на поведение приращения функции. Если для любых точек х и х", принадлежащих отрезку [а, b], приращение функции удовлетворяет неравенству

½f(x) - f(x")½ £ М½х - х"½a

где 0 < a £ 1 и М - некоторая постоянная, то говорят, что функция f(x) удовлетворяет условию Липшица порядка a на отрезке [a, b], и пишут: f(x) Î Lipa. Каждая функция, удовлетворяющая при каком-либо a > 0 Липшица условие на отрезке [а, b], равномерно непрерывна на [а, b]. Функция, имеющая на [а, b] ограниченную производную, удовлетворяет на [а, b] Липшица условие с любым a £ 1. Липшица условие впервые рассмотрел в 1864 нем. математик Р. Липшиц (R. Lipschitz; 1832 - 1903) в качестве достаточного условия для сходимости ряда Фурье функции f(x). Иногда, исторически неправильно, связывают с именем Липшица только наиболее важный случай Липшица условие с a = 1, а в случае a < 1 говорят об условии Гёльдера

20. Метод дихотомии

Нам необходимо найти корень уравнения f(x)=0 на отрезке [a, b].

Рассмотрим отрезок [x0, x1]: [x0, x1]([a, b]. Пусть мы нашли такие точки

х0, х1, что f (х0) f(х1) ( 0, т. е. на отрезке [х0, х1] лежит не менее

одного корня уравнения. Найдём середину отрезка х2=(х0+х1)/2 и вычислим

f(х2). Из двух половин отрезка выберем ту, для которой выполняется

условие

f (х2) f(хгран.) ( 0, так как один из корней лежит на этой половине. Затем

новый отрезок делим пополам и выберем ту половину, на концах которой

функция имеет разные знаки, и т. д. (рис 1.2).

Если требуется найти корень с точностью Е, то продолжаем деление пополам до тех пор, пока длина отрезка

не станет меньше 2Е. Тогда середина последнего отрезка

даст значение корня с требуемой точностью.

Дихотомия проста и очень надёжна. К простому

корню она сходится для любых непрерывных функций

в том числе и не дифференцируемых; при этом она устой-

чива к ошибкам округления. Скорость сходимости не ве-

лика; за одну итерацию точность увеличивается пример-

но вдвое, т. е. уточнение трёх цифр требует 10 итераций.

Зато точность ответа гарантируется.