Содержание к диссертации
Введение
ГЛАВА 1. Численные методы решения уравнений и вычисления значений функций. обзор (анализ) 15
1.1. Методы решения линейных скалярных уравнений 16
1.2. Решение уравнений при помощи цепных дробей 29
1.3. Вычисление значений функций 33
Выводы 43
ГЛАВА 2. Разработка итерационных методов при помощи цепных дробей 44
2.1. Методы, основанные на разложении функции в цепную дробь 44
2.2. Методы, основанные на разложении в цепную дробь функции, обратной данной функции 55
2.3. Методы, основанные на представлении функции таблицей Паде 66
2.4. Методы, основанные на представлении функции, обратной к функции /(х), таблицей Паде 76
2.5. Методы, основанные на аппроксимации функции интерполяционными цепными дробями 81
Выводы 94
ГЛАВА 3. Разработка методов вычисления значений функций 97
3.1. Методы, основанные на разложении функции в цепную дробь 97
3.2. Методы, основанные на разложении в цепную дробь функции, обратной данной функции 104
3.3. Таблица Паде для отношения степенных рядов 111
3.4. Аппроксимации Паде для тригонометрического ряда Фурье и ряда, сопряженного с ним 117
3.5. Комбинированное приближение функций двух переменных 119
3.6. Комбинированное интерполирование функции двух переменных 125
Выводы 130
ГЛАВА 4. Разработка прямых методов решения систем линейных алгебраических уравнений с матрицами специальной структуры 131
4.1. Вычисление определителей трехдиагональных матриц с помощью цепных дробей 131
4.2. Решение систем линейных уравнений с трехдиагональной матрицей 134
4.3. Вычисление определителей почти треугольных матриц при помощи цепных дробей 135
4.4. Решение систем линейных уравнений с почти треугольной матрицей 138
Выводы 139
Заключение 141
Список использованной литературы
- Решение уравнений при помощи цепных дробей
- Методы, основанные на разложении в цепную дробь функции, обратной данной функции
- Методы, основанные на разложении в цепную дробь функции, обратной данной функции
- Решение систем линейных уравнений с трехдиагональной матрицей
Введение к работе
Объектом исследования данной диссертационной работы являются бесконечные цепные дроби, т.е. выражения вида
и = Ь0+ ^ .. (1)
ь,+ ^
' ь1+ а>
а.,
+ -
Ь„+...
В большинстве зарубежных работ вместо «цепная дробь» употребляется название «непрерывная дробь». Мы будем использовать оба названия. Величины bQ,b{,b2,...,bn,...,a{,a2,...,an,... называются элементами цепной дроби. В
частности а]ьа2,...,ап,... называются частными числителями, Ъ^Ъ2,...,Ьп,... - частными знаменателя цепной дроби (1); Ь0 - ее свободным членом. Дробь —
называется л-м звеном цепной дроби (1).
Для записи цепной дроби (1) будем пользоваться предложенной Роджерсом формой
со = 60+^+...+ ^ + ... (2)
Для большей компактности будем использовать и такое обозначение
,ы ьп введенное Хлопониным С.С. Конечная цепная дробь
"а, , а, си а,, /А.
/=іЬ; ъх ь2 ъ„
называется и-ой подходящей дробью цепной дроби (1) и обозначается f„=AnIBn. Таким образом, цепной дроби соответствует последовательность
подходящих дробей:
4l A. :di A. (S)
в0'вх'в2'-вГ ( j
Изучение конечных цепных дробей, т.е. выражений вида
(6)
bi+ -_
b2 +
b}+...
началось в конце XVI в. в статье Бомбелли [2]. Выражения вида (6) получаются при повторном применении алгоритма Евклида. Некоторые историки математики утверждают, что использование выражений вида (6) восходит к индийской или даже греческой математике. Бесконечные цепные дроби впервые были рассмотрены лордом Броункером (1620-1684), первым президентом Королевского общества. Ему принадлежит представление числа п в виде бесконечной цепной дроби:
7Г_ 1
2 + І.
2 + -
2 + ...
2 + ...
В теории непрерывных дробей сложилось два направления: теоретико-числовое и аналитическое. Теоретико-числовое направление занимается изучением непрерывных дробей с частными числителями ап =1 и целыми положительными частными знаменателями [89]. В этом направлении непрерывные дроби использовались для рационального приближения значений алгебраических чисел и числа к. Применение непрерывных дробей в теории чисел началось в XVII веке работами Швентера, Гюйгенса и Валлиса, достигло крупных результатов в работах Эйлера и затем было расширено Лагранжем, Лежандром, Гауссом, Галуа и их последователями.
Аналитическое направление исследует цепные дроби более общего вида: в аналитической теории рассматриваются цепные дроби, элементы которых - линейные и полиномиальные функции комплексного аргумента. Здесь
требуется лишь одно - элементы цепной дроби должны принимать только конечные значения, если не будут указаны более конкретные ограничения.
Разложения функций комплексного переменного в цепные дроби были введены Эйлером и стали важным средством аппроксимации специальных классов аналитических функций в работах Эйлера, Ламберта, Лагранжа. Гауссом было введено в 1813 г. разложение в непрерывную дробь для отношения гипергеометрических функций [23, 97]. Как следствие этого результата появились ортогональные многочлены.
В прошлом веке различие целей теоретико-числового и аналитического приложений аппарата непрерывных дробей привело к раздвоению развития теории. Одна из возникших ветвей - аналитическая теория цепных дробей. Основной предмет ее исследований - теория разложения и сходимости непрерывных дробей, элементами которых являются линейные функции комплексного переменного z. Эти исследования важны потому, получающиеся при этом конечные цепные дроби представляют собой рациональные функции от z, аппроксимирующие функцию f{z) и дающие разложения в смысле Эрмита в классе рациональных функций.
Аналитическая теория цепных дробей занимала ведущее положение в классическом анализе 19 века. В этой области работали крупнейшие аналитики: Лаплас, Лежандр, Якоби, Эйзенштейн, Гейне, Лаггер, Риман, Стилтьес, Чебышев, Марков, Фрбениус и Пуанкаре. Их исследования оказали далеко идущее влияние на развитие математики. Особенно это относится к работам Стилтьеса, которые привели к таким важным исследованиям, как проблема моментов, теория интеграла Стилтьеса, изучение сходимости последовательностей гомоморфных функций. В работах Пуанкаре и Стилтьеса, в которых применялись разложения в цепные дроби к расходящимся рядам, появились асимптотические разложения.
Таким образом, влияние теории цепных дробей на развитие классического анализа в XIX веке оказалось особенно плодотворным. Были периоды, когда в XX веке аналитики, работающие в наиболее классических областях,
7 стали редко интересоваться цепными дробями и теория непрерывных дробей стала специальным разделом, в котором работал ограниченный круг аналитиков.
В 60-70-х гг. XX века произошел бурный 'рост применения цепных дробей в физических проблемах. Аппроксимации Паде стали главным вычислительным средством в задачах теоретической физики, что привело к оживлению в теории цепных дробей. Как отклик на эти события появилось несколько монографий по цепным дробям [23, 11, 1, 14, 82].
Приведем некоторые проблемы, решение которых поясняет плодотворность использования непрерывных дробей в вычислениях.
1) Цепные дроби дают более общие представления (разложения)
трансцендентных функций, чем классическое представление степенным ря
дом. Например, степенной ряд для мероморфной -функции в точке х пред
ставляет эту функцию только до ближайшего полюса; для некоторых меро-
морфных функций существуют представления цепными дробями, которые
представляют эту функцию всюду на комплексной плоскости, за исключени
ем полюсов. Таким образом, область сходимости цепной дроби, представ
ляющей некоторую функцию, может быть шире области сходимости степен
ного ряда, представляющего ту же функцию.
2) Разложение функции в цепную дробь сходится в данной точке х бы
стрее, чем степенной ряд для той же функции.
Функция arctgz имеет следующее разложение в непрерывную дробь:
, 12 „2 ->2 ,2 ->2 „2 л2 _2
arctgz = -, . . . .... {/)
^ 135 79
Эта дробь сходится на всей плоскости комплексного переменного z, исключая полуинтервалы МНИМОЙ ОСИ (-/со,-/], [/,оо/).
Разложение в ряд Тейлора функции arctgz в точке z = О
7, 5 7 9
Z Z Z Z
arclgz = z + -——+ -—... (8)
8 сходится при |z|
с ошибкой, не превышающей 10~7, нужно просуммировать члены до (приблизительно) степени 106 разложения (8). Можно показать, что arctgi может
быть вычислен с ошибкой, меньшей КГ7, с использованием 9-ой подходящей дроби цепной дроби (7).
3) Известно приложение, которое непрерывные дроби находят в теории
управления. Сущность в следующем. Необходимо установить устойчивость
полинома с вещественными коэффициентами, т.е. будут ли все его нули
иметь отрицательные вещественные части. Отвечают на этот вопрос за ко
нечное число шагов и без вычисления самих нулей следующим образом.
Возьмем для определенности многочлен шестой степени
Р(х) = а0 +а[х + а2х2 +... + аьх'\ Строим рациональную функцию
аа+а2х +а4х +аьх используя коэффициенты полинома Р(х). Функция R(x) называется тестовой функцией устойчивости полинома. При помощи известного алгоритма функцию R(x) можно представить в виде цепной дроби
охх о2х Ь()х Данный полином устойчив в том и только в том случае, когда все Ь, > 0.
4) В прикладной математике результаты решения задач получаются в
виде асимптотических рядов вида
/(x)~A+l + ^ + .„, Х->Х,
при чем ряд расходящийся при всех х. Оценку /(х) при помощи такого ряда нельзя получить с произвольной точностью для любого значения х. И здесь помогают цепные дроби. Асимптотический ряд обращают (алгоритм обращения известен) в цепную дробь вида
Находят, что цепная дробь сходится и что она действительно представляет искомую функцию f{x). Этот подход, к сожалению, является, эмпирическим.
Аппроксимационные и интерполяционные цепные дроби качественнее описывают приближаемые функции вблизи тех точек, в которые функции обращаются в бесконечность [5, 8, 23, 97].
Свойство цепных дробей мало накоплять погрешность с ростом числа звеньев цепной дроби имеет огромное значение для вычислительной математики [14, 23, 82, 66].
Так как теория цепных дробей обладает рядом замечательных свойств (рядом преимуществ) по сравнению с теорией степенных рядов, то целесообразно конструировать на основе теории цепных дробей эффективные численные методы, предназначенные для приближения функций (как одного, так и многих переменных) и решения уравнений. Проблема построения эффективных численных методов для решения задач алгебры, анализа, дифференциальных уравнений является актуальной.
Таким образом, предметом данного исследования являются численные методы, построенные на основе теории непрерывных дробей.
Целью диссертации является конструирование численных методов приближения функций и решения уравнений, доказательство их сходимости, вывод остаточных членов, выяснение скорости сходимости, сравнение на эффективность полученных методов и известных методов, предназначенных для решения тех же задач.
Поставленная цель требует решения следующих задач:
Построить итерационные методы уточнения отделенных простых вещественных корней скалярного уравнения f{x)= 0.
Приспособить полученные итерационные методы уточнения корней уравнения /{х)=0 для вычисления приближенных значений функций.
Обобщить таблицу Паде для отношения степенных рядов.
Построить таблицу Паде для тригонометрического ряда и ряда, сопряженного с ним.
Разработать комбинированные методы приближения функций двух переменных (аппроксимационный и интерполяционный).
Разработать методы вычисления определителей трехдиагональных и почти треугольных матриц.
Разработать прямые методы решения систем линейных алгебраических уравнений с трехдиагональными и почти треугольными матрицами.
Методология и методы проведенных исследований. Решение поставленных задач основывается на использовании теории чисел, алгебры, численных методов и алгоритмов, рядов и непрерывных дробей.
Для целей исследования были использованы следующие типы цепных дробей:
а) правильные С-цепные дроби (дробь Тиле) [8, 5, 23, 97];
б) присоединенные цепные дроби [23, 97, 82];
в) таблица Паде [4, 10];
г) интерполяционные цепные дроби [7, 73, 90, 30, 82];
д) восходящие цепные дроби [3, 99].
Достоверность и обоснованность полученных в диссертационной работе теоретических результатов и формируемых на их основе выводов обеспечивается строгостью проводимых математических доказательств. Справедливость выводов относительно эффективности предложенных методов подтверждена численными расчетами.
Научная новизна полученных результатов заключается в следующем:
Разработаны итерационные методы высокого порядка для решения нелинейных скалярных уравнений.
Итерационные методы решения нелинейных скалярных уравнений приспособлены к вычислению приближенных значений функций одного переменного.
Показано, что аппарат цепных дробей является более плодотворным источником получения новых итерационных процессов, чем аппарат степенных приближений.
Показано, что аппроксимации Паде обладают самыми мощными аппрок-симационными возможностями для конструирования итерационных процессов высокого порядка по сравнению с другими типами цепных дробей.
Таблица Паде обобщена для отношения степенных рядов.
Построена таблица Паде для тригонометрического ряда и ряда, сопряженного с ним.
Предложены два комбинированных метода приближения функций двух переменных: аппроксимационный и интерполяционный.
Разработан метод вычисления определителей трехдиагональных матриц при помощи цепных дробей.
Разработан прямой метод решения систем линейных алгебраических уравнений с трехдиагональной матрицей, основой которого является представление конечной восходящей цепной дробью первой либо последней координаты вектора решения.
10.Получено представление для определителей с почти треугольными матрицами в виде произведения конечных восходящих дробей.
11.Разработан прямой метод решения систем линейных алгебраических уравнений с почти треугольной матрицей, основой которого является представление конечной восходящей цепной дробью первой либо последней координаты вектора решения.
Практическая значимость полученных результатов.
1. Разработанные методы численного решения уравнений могут быть с успехом применены для математических моделей, основой которых являются нелинейные скалярные уравнения; дифференциальные уравнения как обыкновенные, так и в частных производных, сводящиеся к разностным схемам; системы линейных алгебраических уравнений как с матрицами специальной структуры, так и с матрицами общего вида.
Разработанные методы вычисления определителей матриц специальной структуры могут быть использованы в различных областях прикладной математики.
Разработанные методы приближения могут быть применены для вычисления приближенных значений функций, заданных аналитически или дискретно (таблично).
Некоторые результаты работы внедрены в учебный процесс Ставропольского, государственного университета: ведется дисциплина по выбору «Применение теории цепных дробей в вычислительной математике» для студентов старших курсов физико-математического факультета специальностей «Прикладная математика и информатика» и «Математика».
Основные положения диссертации, выносимые на защиту.
Итерационные методы уточнения отделенных простых действительных корней скалярного уравнения f(x) = 0, построенные на основе цепных дробей.
Итерационные методы вычисления приближенных значений функций одного переменного, построенные на основе цепных дробей.
Обобщение таблицы Паде для отношения степенных рядов.
Таблица Паде для тригонометрического ряда и ряда, сопряженного с ним.
Комбинированные методы приближения функций двух переменных.
Методы вычисления определителей трехдиагональных и почти треугольных матриц при помощи конечных непрерывных дробей.
Прямые методы решения систем алгебраических уравнений с трехдиаго-нальными и почти треугольным матрицами при помощи конечных восходящих дробей.
Апробация результатов диссертации. Результаты исследований докладывались:
1. На заседаниях научно-методического семинара кафедры прикладной математики и информатики Ставропольского государственного университета (1978 г., 1980 г., 1982 г., 1995-1998 гг., 2003-2006 гг.).
На заседаниях научного семинара «Цепные дроби» (1972-1975 гг., 1977-1982 гг.).
На научных конференциях преподавателей и студентов Ставропольского государственного университета (1995-2006 гг.).
На научно-методической конференции по математике преподавателей педвузов (г. Махачкала, 1975 г.).
На Всесоюзной научной конференции «Цепные дроби и их применение» (г. Львов, 1975 г.).
Опубликованность результатов. Материалы диссертации опубликованы в 20 научных работах.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы (содержащего 103 наименования). Основная часть работы изложена на 152 страницах машинописного текста, содержит 21 таблицу.
В первой главе проведен анализ различных методов: решения скалярных уравнений, основой построения которых являются полиномиальные приближения, и все эти методы - итерационные; решения дифференциального уравнения Риккати при помощи цепных дробей различных типов; решения систем линейных алгебраических уравнений, основой конструирования которых являются как ветвящиеся цепные дроби, так и обыкновенные; приближения функций одного и многих переменных цепными дробями различных типов - многие из этих методов являются итерационными.
Во второй главе строятся итерационные методы решения скалярных уравнений на основе разложения функции в цепную дробь; на разложении в цепную дробь функции, обратной данной функции; на представлении функции таблицей Паде; на представлении функции, обратной данной, таблицей Паде; на интерполировании данной функции и ей обратной цепной дробью.
Для каждого метода: доказывается его локальная сходимость, строится погрешность метода на одном шаге, устанавливается скорость сходимости.
Показано также, что таблица Паде есть мощный аппроксимационный
14 инструмент конструирования новых итерационных процессов высоких порядков.
Приводятся численные расчеты, подкрепляющие полученные теоретические результаты. В частности, получен обнадеживающий результат: производные высоких порядков, участвующие в итерационном процессе, можно аппроксимировать разделенными разностями с довольно большим шагом /?, что помогает избежать вычитания двух близких чисел - нужно только позаботиться о том, чтобы производная итерационной функции (р(х\ф(х)) была по модулю меньше единицы в окрестности корня \.
В третьей главе строятся численные методы для вычисления значений функций одной и двух переменных на основе: разложения данной функции и ей обратной в цепную дробь; представления данной функции и ей обратной таблицей Паде.
Таблица Паде обобщается для отношения степенных рядов. Строится таблица Паде для тригонометрического ряда и ряда, сопряженного с ним. Разрабатываются: комбинированная аппроксимация функции двух переменных тейлоровским многочленом и цепной дробью; комбинированная интерполяционная формула для функции двух переменных лагранжевым полиномом, правильной С-цепной дробью или присоединенной цепной дробью.
Приведены численные расчеты, подкрепляющие полученные теоретические результаты. Продемонстрировано, что вблизи точек, в которых приближаемая функция обращается в бесконечность, аппроксимации цепными дробями дают больший выигрыш в точности, чем многочленные аппроксимации.
В четвертой главе разрабатываются методы вычисления определителей трехдиагональных и почти треугольных матриц, прямые методы решения систем линейных алгебраических уравнений с матрицами специальной структуры на основе обыкновенных и восходящих цепных дробей.
В заключении приведены основные результаты диссертационной работы.
Решение уравнений при помощи цепных дробей
В виде цепных дробей представляются решения обыкновенных дифференциальных уравнений [11, 23, 68, 97]. Метод решения дифференциальных уравнений с помощью цепных дробей предложен Эйлером и развит Ла-гранжем. Он заключается в следующем.
Пусть дано дифференциальное уравнение, связывающее, например, у,у ,х, и пусть для малых х y zt. Положив y = z]/(\ + y]) и подставив в ис зо ходное уравнение, получим тем самым дифференциальное уравнение, связывающее у1,у\ и х. Пусть ух «z2 при малых х. Положив yt=z2/(\ + y2), получим дифференциальное уравнение, связывающее у2,у2 и х. Продолжая этот процесс, в итоге получим решение дифференциального уравнения в виде цепной дроби y=Z —. «-і і Величины z" Лагранж предложил искать в виде а„ха, где а„ - целые положительные числа. Обычно z" ищут в виде апх.
Большой вклад в развитие этого метода внесли Санилевичи и Хованский. В монографии А.Н. Хованского [97] этот метод является главным в получении разложений функций в цепные дроби.
Наиболее общее дифференциальное уравнение, решенное методом Ла-гранжа, есть уравнение (а + а х)хУ+(р + $ х)у + уу2 = 8х, (1.2.1) называемое основным дифференциальным уравнением [97]. Оно решено путем применения последовательной подстановки У. -7м- (п 0,у0,у), (1.2.2) J + JVi приводящей к правильной С-цепной дроби.
Хлопонин С.С. [95] для решения дифференциального уравнения (1.2.1) применил более общую подстановку .=7- {п 0,Уо=у), (1.2.3) Ь„+с„х + у„.х где а„,Ь„,сп - неопределенные коэффициенты. С помощью этой подстановки получены не только известные разложения в цепные дроби для решения уравнения (1.2.1), но и целый ряд новых.
В работе [95] С.С. Хлопонин при помощи (1.2.3) решил уравнение Ра(х)ху+Рь(х)у+Рс(х)у2=Ра{х)х, (1.2.4) где Ри{х\Рс{х),РАх) - многочлены степени к, Ph(x) - многочлен степени к + \. В работе [95] С.С. Хлопонин с помощью подстановки Уя=- — (1-2.5) і„х + У«+і находит решение дифференциального уравнения Pa{x)xy +Ph{x)y+Pc{x)y2 = PAx)x, (1.2.6) где Pa(x),Ph(x),Pc(x) - многочлены степени к, Pj(x) - многочлен степени к + \ , в виде цепной дроби Стилтьеса [83].
Хлопонина Э.П. в работе [96] с помощью подстановки Уп= 1 (и== 0,1,2,..., v ()) (1.2.7) с«+У«+\ находит решение дифференциального уравнения Рйкатти (а + а х + апх2)у +{р + рх)у + уу2 =5 + 8 х (1.2.8) в виде цепной дроби ю a +h х y=Z , (1.2.9) частными случаями которой являются известные разложения. В работе [54] решение дифференциального уравнения Рйкатти (а + а х)д-/+(р + fix)y + уу2 = 5 ищется с помощью цепной дроби вида , b„+c„x n n
Если в этой цепной дроби х заменить на -, то мы получим сжатую в два х раза правильную С-цепную дробь (присоединенную дробь).
2. В работах [14, 16, 82] решения конечно-разностных уравнений и дифференциальных уравнений как обыкновенных, так и в частных производных ищутся в виде цепных дробей (обыкновенных и ветвящихся). Можно показать, что метод прогонки эквивалентен вычислению конечной цепной дроби [82].
3. В работах [74, 75] построены алгоритмы решения невырожденных систем линейных алгебраических уравнений общего вида
Методы, основанные на разложении в цепную дробь функции, обратной данной функции
1. Для отыскания действительных корней уравнения f(x)-0 П.Л. Че-бышев предложил метод, в основе которого лежит представление функции, обратной к функции /( ), по формуле Тейлора [98, 12].
В теории цепных дробей ряду Тейлора (2.2.1) ы\ соответствует репная дробь Тиле [68, 97] h h (2.2.2) f{x + h) = f{x)+ Ш + Ш++/„(хГ где fx(x), f2(x),..., fn(x) - обратные производные функции f(x), определяемые формулами: /,М= ,Ш=Л ) (2.2.3) В основе предлагаемого способа отыскания корней уравнения /(л) = 0 лежит представление функции, обратной к функции /( ), в виде конечной цепной дроби Тиле. 2. Рассмотрим нелинейное уравнение /(х) = 0. (2.2.4)
Пусть уравнение (2.2.4) имеет на отрезке [а,р] единственный корень х = х. Будем считать, что функция f(x) непрерывна на отрезке [а, ] вместе со своими производными достаточно высокого порядка, / ( ) 0. Тогда при этих условиях функция y = f(x) имеет на [сс,р] обратную функцию х = \\/(у), определенную на отрезке [ х ,р ] и имеющую там столь же непрерывных производных, что и f(x).
Очевидно, что = = v(o). (2.2.5) При фиксированном у є [а ,/? ] конечная формула Тиле и формула Тейлора дадут следующие представления для функции х = у/{у) соответственно: - = )+ - -- + 4, (2-2-6) w) хъ_\у) v,\y) x = ± (Y-y) + R2. (2.2.7) Здесь y/jiy) -обратные производные функции //( ). Учитывая (2.2.5), из формул (2.2.6) и (2.2.7) получим соответственно: = )-4-4-- -..,- + 4, (2-2.8) =у(у)+ЁИ У +(-1Г У + , (2.2.9) Так как x = v\f(x)] то разложения (2.2.8) и (2.2.9) примут вид: .г + ( + ,( /-( ), (2.2.11) где обозначено /! Цепная дробь (2.2.10) обладает тем свойством, что разложение ее к -ой (к п) подходящей дроби по формуле Тейлора совпадает с разложением (2,2,11) до члена ак(х)/к(х) включительно, т.е. W\x)\ м НО Вы(х)/ы( ) «М/ы(х) Пусть л,[/Ь)]=х__ /W /W /(х)
Тогда остаточный член в разложении (2.2.10) может быть записан в следующей форме [91]: .= , 1Г ч ) RifY Г, где R{f)-f"+] есть остаток от формального деления многочлена Л„(/) на многочлен 5,,(/) по степеням /, когда в частном получен член с /"+, и разложение (2.2.10) примем вид: х = х + f f f ml ,(/) (/) " „(/) (2.2.12) Положим ф(х) = x + f f f V,(/) 2(/) " ,,(/) Уравнение имеет корень x = x т.к. x = ф(х) v,(f) v,if) vAf) Положив теперь .. = ( J (т = 0,1,2,.., „ є [о,pj, (2.2.13) получим итерационный процесс (« + 1)-го порядка, т.к. Ф (х) = 0 (/ = й). Так как Ф (х) = 0, то существует такая окрестность точки х (в силу локальной непрерывности Ф (х)), в которой \Ф {х) \, и, следовательно, для сходимости последовательности {хш} к корню х нужно взять начальное приближение х0 из этой окрестности.
Оценку погрешности и скорость сходимости итерационного процесса (2.2.13) получим из (2.2.12), где полагаем х = хт: Х Хпп\ (_irv(et,,fe2) R(f( J) (/i + l) /Ц/( Д / (О (2.2.14) $2 Є ( , „) Пусть Ч = max «[or,/?] (- 1) (и + l) Я,(/(х)). (2.2.15) хе[а,р] Имеем также следующее соотношение \fM=ift,K-xUM2-K-x\, %і е{х хЛ Теперь из формулы (2.2.14) с учётом (2.2.15) и (2.2.16) будем иметь \х-хт \\-М\ Мг \х хтЛ =P-\X-X„J (2.2.16) (2.2.17) где p = M,-A/f. Оценка (2.2.17) показывает, что полученный итерационный процесс (2.2.13) имеет такую же скорость сходимости, как и итерационные процессы П.Л. Чебышева. Функцию Ф{х) можно найти в явном виде через f(x) и её производные. Для этого сначала надо найти в явном виде функции ак(х), пользуясь формулами обращения степенного ряда, а потом найти функции і/„(/(х)) по формулам (2.2.3).
Методы, основанные на разложении в цепную дробь функции, обратной данной функции
1. Одним из видов приближения функций является приближение их рациональными функциями. Основным источником получения таких при ближений являются цепные дроби [5, 23, 68, 97]. Существуют и методы не посредственного получения рациональных приближений данной функции, не разлагая ее в цепную дробь. В этом отношении следует указать прежде всего метод, основанный на интегральной формуле Обрешкова [97], метод итера ций, приспособленный для этих целей [97], и метод Паде построения для степенного ряда рациональных приближений [11, 5].
Метод Паде не удобен в тех случаях, когда разложение функции в степенной ряд является сложным (например, для tgx). Для таких функций нередко известны представления в виде отношения степенных рядов. Поэтому естественно обобщить метод Паде, получив формулу приближения рациональными функциями для отношения степенных рядов. Такая формула предлагается в данном параграфе. Ясно, что такой подход позволяет получать рациональные приближения и для степенных рядов.
2. Пусть дано отношение степенных рядов М = (а0 0Д 0). (3.3.1) ІМ" Поставим задачу: найти такое приближение для отношения (3.3.1) в виде рациональной функции где Рк{х) и Q,{x) -многочлены степени к и / соответственно, что разложения в степенные ряды для них совпадают между собой до степени к + l включительно.
Из условия поставленной задачи следует, что разложение в степенной ряд для выражения 112 начинается со степени к +1 +1, то есть имеет вид со а"х" Р(х) л=о Гк\Л) _ Yk+i+\sr ,-1 Обозначим лМ=Еа, е,М=ІР, - (3.3.3) i=0 ыо Теперь последнее равенство перепишем так: / СО к СО / S: СО р/ ; „ " -2 / %ь.х = м -р/ fry ЪСЫ„Х -] i=0 я=0 ,=0 »=0 (=0 н=0 ,=1 Если воспользоваться формулой произведения двух рядов, то получим равенство: tti jK -Ь,анУ=хк -р/±Ьпх".±сы , (3.3.4) ,»0 0 ,=0 11=0 ,=1 где (},_,. =0 для i-j l, a,_j =0 для i-j k. В левой и правой частях равенства (3.3.4) стоят ряды, причем ряд в правой части начинается со степени не ниже к + 1 + \. Следовательно, коэффициенты ряда левой части при степенях 0,1,2,...,к+1 равны нулю: Ё(а$н-Ь,а1Ч)=0 для / = 0,1,2,..., +/, j=0 или — о0сс0 = —а0р0, а0Р, - ctg-Ь0а, =-л,р0, а.р.+АоРз- ао- а боаз =-а2р0, (3.3.5) Напоминаем, что а; = 0 для / , р, = 0 для / /.
Считая в системе (3.3.5) р0 0 любым заранее заданным, что не повлияет на значение выражения (3.3.2), мы будем иметь систему к +/ + 1 линейных уравнений с к+ 1 + 1 неизвестными.
2. Оценим остаточный член рассматриваемого приближения.
Если функция f(x) непрерывна в промежутке [-п,п] вместе со своими г-\ первыми производными /(w)(x) (w = 0,l,...,r-l) (имеющими ограниченное изменение), удовлетворяет на концах промежутка вместе с этими же производственными условиями /(" )(-л+0)=/(ш,(я-0) (/н = 0,1,...,/--1) и имеет производную f{r\x) с ограниченным изменением, то справедлива следующая оценка [32]
Комбинированное приближение функций двух переменных
Для приближения функций наиболее часто используются многочлены. Однако это не единственный возможный вид приближения.
Многочленные формулы приближения неприменимы вблизи точек, в которых приближаемая функция обращается в бесконечность.
Формулы приближения, полученные с помощью непрерывных дробей могут быть успешно использованы для аппроксимации разрывных функций [97, 82].
Трудоёмкость решаемых задач резко возрастает с ростом размерности решаемых задач. Предлагается следующий подход к приближению функций двух переменных.
1, Рассмотрим функцию /( ) =/(х,, ,), заданную на открытом множестве Псі?2 и имеющую на Q непрерывные частные производные того порядка, который нужен, чтобы имели место формулы, о которых будет идти речь ниже.
Зафиксируем точку х(0) = (xf0), х{20]) и пусть 8 0 есть достаточно малое число, чтобы все точки х = (х1,х2) из её окрестности -x\ (xl-x\0)J + (x2-xPj Ь принадлежали Q.
Пусть функция /(х,,х2) определена и достаточное число раз непрерывно дифференцируема в окрестности точки (х[0), xf ).
Мы хотим, используя значения функции /(х,,х2) и её производных до некоторого порядка в точке (х,(0 , xf ) представить /(х,,х2) в виде суммы не 120 которого аппроксиманта и остаточного члена, который становится очень малым, когда точка (х,,х2) приближается к (xf0 , xf}).
Решение систем линейных уравнений с трехдиагональной матрицей
Системы линейных алгебраических уравнений с трехдиагональной матрицей решаются обычно методом прогонки [81]. Можно показать, что метод прогонки эквивалентен методу обыкновенной цепной дроби [82].
Предлагается новый метод решения систем с указанной матрицей, основой которого являются как восходящие дроби, так и обыкновенные. Пусть дана система линейных уравнений с трехдиагональной матрицей я, Ъх О О с2 аг Ъг О О с3 а2 Ьг 0 0 0 0 0 0 0 1 А 0 0 х2 /г 0 0 , = /з 1 а„-\ К-\ и-1 /.-, с» "п х« /;, (4.2.1) По формулам Крамера найдем xn: xn=DJK, (4.2.2) где Ап и Д - значения определителей (4.1.2) и (4.1.6). Подставив в формулу (4.2.2) разложения для Дя и Д, получим представление последней координаты вектора решения в виде восходящей цепной дроби, частными знаменателями которой являются обыкновенные дроби:
Если Д 0 (/ = 1,2,...,и), то все действия, необходимые для вычисления цепной дроби (4.2.3), выполнимы. Остальные координаты x„_i,xll_2,...,x2.xl вектора решения х находятся методом обратной подстановки.
По формулам Крамера можно найти сначала х,: =A-A.v -...- ArAAi (4-2-4) в, в2 в, - д„_, в„ "" 6 с где Вп=ап,ВіЛ=аіА—IJ±J-,i = n,n-\,...,2. Остальные координаты х2,х ,...,хп вектора решения х найдем прямой подстановкой. Если В, Ф 0 (/ = 1,2,...,л), то все действия, необходимые для вычисления цепной дроби (4.2.4), выполнимы.
2. Вычисление значения цепной дроби (4.2.3) в пакете MathCad после ввода исходной информации можно организовать следующим образом: Л,:=а, /:=2..я Д д— 4-і / -Р f -Р Р0:=0 /:=1../7-1 :=A_ L.C/+i Р.= Ь ± 4 4,
Здесь в первой строке вычисляются частные знаменатели цепной дроби, во второй строке вычисляется значение Р цепной дроби.
Вычисления значения цепной дроби (4.2.4) можно организовать аналогично.
Для вычисления значений определителей почти треугольных матриц строится представление в виде произведения конечных восходящих цепных дробей. 1. Вычислим значение определителя левой почти треугольной матрицы A.. = Вычитая первый столбец, умноженный на ап /аи, из второго столбца и разложив полученный определитель по элементам первой строки, будем иметь
К вычислению определителей почти треугольных матриц сводятся многие задачи: определение коэффициентов ряда, получающегося при делении двух сходящихся степенных рядов, когда у знаменателя-ряда отсутствуют нули. [71]; нахождение чисел Бернулли; применение итерационных процессов, построенных на основе теоремы Кёнига [12], и др.
На основе результата 4.3. получено разложение в конечную восходящую цепную дробь первой либо последней координаты вектора решения системы линейных алгебраических уравнений с почти треугольной матрицей.
Подставив представления (4.3.4) и (4.4.3) в формулу (4.4.2), получим следующий результат: А Л2 АУ /І Д вычисляются по формулам (4.3.5).
Остальные координаты хі(і = 2,3, ...,п) вектора решения х системы (4.4.1) находятся с помощью прямой подстановки. 2. Пусть дана система линейных уравнений Ax = f, (4.4.5) где А - правая почти треугольная матрица размерностью пхп, х и /- п мерные векторы. Здесь мы получим разложение в восходящую цепную дробь последней координаты хп вектора решения JC : С,(/= 1,2,...,«) вычисляются по формулам (4.3.8). Остальные координаты ,.(/ = н-1, п-2, ...,1) находятся с помощью обратной подстановки. Аналогично можно получить разложение в восходящую цепную дробь первой координаты х, вектора решения х: ),(/ = 1,2,...,/7) находятся по формулам (4.3.10). Выводы
1. Построен метод вычисления определителей трехдиагональных матриц при помощи обыкновенных цепных дробей.
2. Сконструирован прямой метод решения систем линейных алгебраических уравнений с трехдиагоналыюй матрицей, в основе которого лежит представление первой либо последней координаты вектора решения в виде восходящей цепной дроби.
3. Разработан метод вычисления определителей почти треугольных матриц при помощи восходящих цепных дробей.
4. Предложен прямой метод решения систем линейных алгебраических уравнений с почти треугольной матрицей, в основе которого лежит представление первой либо последней координаты вектора решения в виде восходящей цепной дроби, частными числителями которой являются элементы матрицы, а частными знаменателями - восходящие дроби.
