 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Скорость сходимости
|
|
Ранее утверждалось, что если итерационный метод в некотором смысле сходится, то он сходится к решению исходной задачи (2.1). Понятно, что быстрота достижения результата существенно зависит от того, насколько удачно (“близко” к решению) выбрано начальное приближение. В общем случае условия сходимости итерационного метода решения системы линейных алгебраических уравнений определяются следующей теоремой, доказательство которой можно найти, например, в книге [1].
Теорема 2.5. Итерационный метод
сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы 
по модулю меньше единицы.
При практическом использовании итерационных методов важен не только сам факт сходимости последовательности получаемых решений, но и скорость, с которой эта последовательность сходится к точному результату. Если для погрешности используемого метода имеет место оценка вида
,
то говорят, что итерационный метод сходится со скоростью геометрической прогрессии со знаменателем q. Эта оценка показывает, во сколько раз уменьшается начальная погрешность после проведения заданного числа итераций.
Зададим произвольное число k>0 и потребуем, чтобы после выполнения N итераций начальная погрешность уменьшилась не менее, чем в k раз, то есть 
. Это имеет место в случае 
, откуда получаем
.
Целая часть этой дроби будет минимальным числом итераций, необходимым для достижения заданной точности. Выражение 
называется скоростью сходимости итерационного метода. Эта скорость целиком определяется свойствами матрицы перехода 
и не зависит от номера итерации, выбора начального приближения и задаваемой точности. Чем выше скорость сходимости, тем выше производительность выбранного метода решения системы линейных алгебраических уравнений.
Полиномы Чебышёва [13]
Для дальнейшего рассмотрения определим, согласно [8], норму
,
называемую чебышёвской.
Рассмотрим задачу: среди всех полиномов степени N со старшим коэффициентом, равным 1, найти такой многочлен 
, для которого величина 
минимальна. Такой многочлен носит название полинома Чебышёва.
Расмотрим функцию
. (2.15)
Произведем тригонометрические преобразования:
Складывая почленно два последних равенства,
получаем рекуррентное соотношение для построения функции 
. В соответствии с формулой (2.15)
И далее, в соответствии с полученной зависимостью
На рис. 2.4 показаны некоторые полиномы построенной системы.
Рис. 2.4. Полиномы TN(x) при N= 2, 3, 4, 5, 6
Можно заметить, что в общем случае коэффициент при старшей степени определяется следующим образом:
(2.16)
Определим функцию в виде
. (2.17)
Очевидно, что является полиномом степени N со старшим коэффициентом, равным 1.
Определим корни этого полинома:
Поскольку является полиномом степени N, он имеет не более N корней, причем все они различны и лежат на отрезке [-1, 1]:
.
Таблица 2.4
Корни полинома для N=1, 2, 3, 4, 5, 6 и 7
| N=1 | N=2 | N=3 | N=4 | N=5 | N=6 | N=7 |
| 0,707106781 | 0,866025404 | 0,923879533 | 0,951056516 | 0,965925826 | 0,974927912 | |
| - | -0,70710678 | 0,382683432 | 0,587785252 | 0,707106781 | 0,781831482 | |
| - | - | -0,866025404 | -0,382683432 | 0,258819045 | 0,433883739 | |
| - | - | - | -0,923879533 | -0,587785252 | -0,258819045 | |
| - | - | - | - | -0,951056516 | -0,707106781 | -0,433883739 |
| - | - | - | - | - | -0,965925826 | -0,781831482 |
| - | - | - | - | - | - | -0,974927912 |
Вполне очевидно (рис. 2.4), что полиномы принимают экстремальные значения в тех точках, где функция cos() принимает значения +1 или -1.
В этих точках полином принимает чередующиеся по знаку значения 
; при этом чебышёвская норма равна 
.
Лемма 2.2. Пусть существует система точек 
такая, что 
, причем в указанных точках функция 
имеет чередующиеся знаки. Тогда среди всех полиномов степени N со старшим коэффициентом, равным 1, многочлен 
наименее уклоняется от 0.
Доказательство. Пусть существует полином 
степени N со старшим коэффициентом 1 (рис. 2.5), причем
,
то есть 
.
Построим функцию 
, отличную от нуля и являющуюся полиномом степени (N-1).
Рис. 2.5. Графики полиномов Q5(x), S5(x) и их разности 
В точках экстремумов 
имеем
.
Тогда 
и в силу предположения функция R(x) на отрезке [-1, 1] меняет знак N раз, а значит имеет N корней, чего не может быть, поскольку R(x) является полиномом степени (N-1).
Таким образом, утверждение леммы 2.2 доказано.
Поскольку построенный ранее полином Чебышёва удовлетворяет всем требованиям леммы, он является наименее уклоняющимся от нуля на отрезке [-1, 1].
В случае необходимости отыскания полинома, наименее уклоняющегося от нуля на произвольном отрезке [a, b], следует перейти к новой переменной
,
которая теперь принимает значение 
.
В этом случае функция PN(x) принимает вид:
.
Формула (2.16) представляется в виде:
Теперь можно получить полином со старшим коэффициентом 1, то есть полином Чебышёва для отрезка [a, b]:
. (2.18)
Корни этого многочлена определяются аналогично рассмотренному выше случаю:
Очевидно, что в этом случае 
.
Может рассматриваться еще одна задача: найти многочлен степени N, наименее уклоняющийся от нуля на отрезке [a, b] среди многочленов, удовлетворяющих условию 
.
Перенормируем полином (2.18) так, чтобы 
,
,
где 
.
Корни этого многочлена расположены в точках
.
Введем обозначения:
;
Рассмотрим соотношения:
;
- нечетная функция;
- четная функция;
- нечетная функция;
- четная функция;
...
Положим 
, тогда
,
.
Вводя обозначение 
, представим определенный выше коэффициент в виде
.
Теперь очевидно, что построенный полином принимает экстремальные значения, равные
.
Дата публикования: 2015-03-26; Прочитано: 748 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
