1611141236-738b6049e710338c8c4dd43e7bd2b717 (824981), страница 53
Текст из файла (страница 53)
Задача о глобальной сходимости метода Ньютона (Ятпа(е Я.//Вп11. Ашет. МайЬ. Нос. — 1985. — 1т. 13, Ж 2). Будем понимать под римаковой сферой Я множество О комплексных чисел с присоединенным символом оо, а под рациональным эндоморфиэмом Я в себя — отображение г т.+ Р(г)/Я(г), где Р и Я вЂ” многочлены. Рациональный эндоморфизм Ньютона Ату: Я -ь Я, ассоциированный с комплексным многочленом /(х) степени и, определяется известной нам из п. 7 3 4 гл. 6 формулой (12): )у7(г) = г — —, /(г) /'( )' Число ~ Е С С Я является неподвижной тпочкой для )т7у (т.е.
Ату(~) = ~) в точности тогда, когда ( — нуль многочлена /. В этом случае, кстати, значением производной Ф~ будет Ат~(~) = (и-1)/и— число, встретившееся нам в п. 4, б). Метод Ньютона вычисления корня (нуля) многочлена / может рассматриваться как итпграцил отпображения ттту: Ат~~(~о) = ~о, ~ = Ату(~ т) = Ат~ (~о). В математической литературе наших дней пару ()ту, Я) считают динамической систпемой и применяют к ее изучению хорошо развитую технику. Как Уже отмечалось, ~Ать(~)) < 1, и, значит, сУЩествУет окРестность У точки ~ такая, что!пп, №~'(г) = ~ для любой точки г е У.
При этом ~ называется сшоном (или притллгиваюитей неподвижной тпочкой для Атт), а открытое множество В = Ц >о Ат~ ~(У) — бассейном стока ~. Точка а Е О называется стпоком периода й для 264 Нерешенные задача о многоч ванга М~, если Хуь(а) = а и )(Муь)'(а) < 1. ПРи Ь > 1 точки а, ХУ(а),... ..., М~~ '(а) различны, причем в некоторой окрестности У Э се итерации Ф~(г) для г 6 У будут приводить к асимптотическим циклам вокруг а,дну(а),...,Х~ (се), не давая в результате неподвижных точек. А это значит, что если Му обладает стоком периода Ь > 2, то о глобальной сходимости Жу "для почти всех г 6 С' говорить не приходится. Построить многочлен у любой степени и > 3 с периодическим стоком для Лу довольно легко.
Например,при и = 3 таковым является многочлен уо(г) = нг — л + 1. Многочлены, до- 1 г статочно близкие к уо, будут также обладать этим свойством. При и = 2 ситуация совершенно иная. Именно, пусть многочлен Дг) = г~ + ах+ Ь обладает двумя различными корнями ~, О, и пусть Р— прямая, перпендикулярная отрезку [~,п) и проходящая через его середину. Тогда непосредственно проверяется (хорошее упражнение), что для любой точки г Е С ~ Т, т.е, почти всюду, последовательность (Ф)н(г)) сходится к ~ или и.
Пусть, например, у(л) = яг — и, а Е й, а > О. В этом случае В = Ьй — мнимая ось, проходящая через середину отрезка (-Я, ~Я. Так как Фу(Ф) 6 й для любого Ф 6 й и 12+(1 / 82+А Му(е|) = Ы+ . = 1 ~е — ) 6 й, то Ю (г2) 6 Ьй. Значит, 2Ы ~, 21 ) начав с чисто мнимого числа з = Й, мы никогда не сойдем с прямой Т и, естественно, не получим методом Ньютона приближения к Я или -Щ Наоборот, единственное условие Кег ф 0 гарантирует такое приближение, хотя, возможно, и не очень быстрое. Еще одно замечание.
Преобразованием г ~е аг с достаточно большим по модулю а многочлен уе степени и переводится в многочлен ~~(г) = Ьола +... + Ь„такой, что )Ьо~ > ~Ьь~ для всех Ь. Далее, нули и критические точки многочленов ~~ и Л~~ для Л 6 С' одни и те же. Аналогично, Фхб = ФА, а это значит, что при обсуждении метода Ньютона у можно брать из множества Р„(1) нормализованных многочленов, коэффициенты которых по модулю не превосходят 1. По лемме 3 Ь" 3 гл. 6 все нули многочлена у 6 Р„(1) лежат в круге Рг = (г 6 С ~ ф < 2). Пусть Ве = (г 6 С~ 1пп И~(я) = ((г), ~(Дг)) = О) — объединение бассейнов всех стоков для Му. Попросту, Ву— область сходимости метода Ньютона в применении к У'.
Специфика множества Р„(1) дает нам возможность ограничиться рассмотрением пересечения Ву ПРг, площадь которого обозначается о(Ву П Рг). Тогда отношение и(Ву П Рг) е(Ву й Рг) и(Рг) 4я Нерешеииые засечи о мнсеочленае 265 можно интерпретировать как еероятностпь того, что метод Ньютона будет сходиться для случайно выбранной точки из Юз. Мы вплотную подошли к формулировке главной задачи. Положим А„= ппп Ау. Уер ОО Разумеется, О < А„< 1. Согласно замечаниям, сделанным выше, Аз —— 1, в то время как А„< 1 при и > 3.
Требуется доказать, что при любом и имеет место нерееенстлес А„> О. Хорошо бы также оценишь А„кек с1ункцию ош и. Пока не доказано даже, что Аз > О. еЕще' многое имею сказать вам, но вы теперь не можете вместить". Еванг. от Иоанна, 16:12 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Абелеаа группа 140 Автоморфвзм группы 146 — поли 60 Аддитввиая группа кольца 152 Аксиомы векторвого (лииейвого) вростравства 66 — группы 139 — теорви определителей 130 Алгебра как наука 11, 15 — матриц 86 Алгебраическая структура (систе.
ма) 134 Алгебреически замкиутое поле 232 Алгебраический элемевт 184 Алгебраическое дополиевие 110, 129 Алгоритм деления 63, 187 — Евклида 194 Аргумеит комплексвого числа 170 Ассоциативвая бивариая операцш 135 Ассоциативное кольцо 152 Ассоциироваииае однородная система 20 Ассоциированные злемевты 61 Аффиввые преобрезовавия веществеивой прямой 150 Базис векторного простравства строк 69 — ввдукцви 46 Базисные столбцы 76 Биективвое (еэаюэво одиозвачвое) отображение 36, 38 Биварная алгебраическая операцил 134 Бивариое отиошеиие 41 Бикоэашльиая формула 48 Бивомиальвый коэффвциеит 48 Блоки (клетки) матрицы 100 Вектор критических зиачекий 263 Векториое пространство строк (столбцов) 66 Векторы — строки 66 Вероятиоствый вектор — столбец 98 Вероятность 265 Верхняя треугольиая матрица 25 Вес миогочлева 221 Вещестаеввая ось 169 Взавмкая (присоедивеввая) матрвца 121 Взаимно простые числа 63 — — элемеиты целоствого кольца 193, 195 Взаимный мвогочлеи 257 Включение мвожеств 34 Вырожденная матрица 87 Высшие член миогочлеиа 222 Гипотеза Нагаты 260 Главная диагональ квадратной матрицы 20 Главные вевзвествые 24, 76 Гомоморфвэм групп 147 — колец 156 График фувкцви 41 Группа 139 — авутревнвх аатоморфвзмов 147 — симметрий правильного мвогоугольвика 142 Предметмыб указатель 267 Двойная сумма 73 Двойное отношение четверок чисел 177 Декартова степень 35 Декартово произведение 35 Делимость з целостных кольцах 190, 192 Делитель единицы з кольце 158 — нуля з кольце 158 — целого числа 61 Диагональная матрица 20 Динамическая система 263 Днскрнминант алгебраического ураввеник 227 — многочлена 227 — семейства элементов 227 Дистрибутивные законы кольца 83 Дифференцирование кольца 213 Дополнение к подмножеству 35 Дробь 159, 203 — несократимая 203 Евклидова кольцо 194 Единичная матрица 20 Единичное (тождественное) отображение 36 Единичный элемент 135 Естественное отображение 42 Закон сокращения в целостном кольце 158 Знак (сигнатура,четиость)перестановки 61 Знакопеременнея группа 148 Изоморфизм групп 144 — колец 157 Инверсия относительно перестановки 61 Интерполяционвзя формула Лагранжа 211 — — Ньютона 211 Каноническая проекция 42 Квадратичная (сзерхэксповевциальная) сходвмость 255 Квадратвчное поле 176 Квадратная матрица данного порядка 20, 86 Класс эквивалентности 41 Классы вычетов 155 Код, исправляющий ошибки 18, 165 Кольцо 152 — классов начетов 155 — мпогочлевов 182 — с делением 159 — функций 153 — целых чисел 153 Коммутатвввзя диаграмма 37 Коммутатнвиое кольцо 152 Комплексное сопряжение 170 Комплексные числа 169 Композвцвя отображений 37 Компонента решеввя 21 Консервативный многочлеи 262 Конструктивные числа и поля 178, 179 Координаты вектора-строки 70 Корень из едввицы 174 Корень (нуль) миогочлева 208 Кососвмметрическая фуикцил 58 Кососиммегрвческвй многочлеи 232 — определитель 116 Коэффициенты мвогочлеиа 183 Кратные множители многочлена 215 Кратный корень 209 Критерий невырождеиности матрвцы 87, 122 — Рауса — Гурзица 252 — совместности линейной системы 77 — Эйзенштейна неприводимости многочлена 200 Критические значения 262 Критические (экстремальные) точки 241, 262 Левонормированное провзведевие 137 Лексикографнческоеупорядочевне одночленоз 221 Предметныб указатель Лемма Гаусса 198 Лемма Даламбера — Аргаиа 235 — Коши о минимуме 234 Линейная зависимость векторов- строк 68 — оболочка 67 — однородная система 20 — система 19 — функшш 80 Линейно зависимая (независимая) система 68 — упорядоченное множество 44 Линейное отображение 79 Линейные комбинацви 67 — уравнения 19 Локэлвзацвя корней мвогочлена 244 Максимэльвый элемент 44 Марковская (стохастическэл) мэ трвца 98 Матрица ливейкого отображения 79 Матричное кольцо 86 Матричные единицы 91 Метод Гаусса 26 — испытаний 254 — линейной интерполяции 254 — неопределенных коэффициентов 225, 242 — Ньютона 255 — окаймляющих мивороэ 126 — последовательного исключения неизвестных 26 — Штрассена 28 Минимальный элемент 45 Минор матрицы 110 Мнимая ось 169 — часть комплексного числа 169 Многочлен (полипом) 182 — Лежандра 258 Множество 33 Модуль комплексного числа 170 — сравнения 155 Моногеввый свмметрическвй многочлев 224 Моноид 135 — цреобразоэаний 136 Мономорфвзм 157 Монотонный одиочлев 222 Морфизм 148 Мощность множества 35, 40 Мультипликативвая групва поля 159 — полугруцпа кольца 152 Наибольший ошцвй делитель 63, 192 — элемент 44 Навменьшее общее кратное 63, 193 Наименьший элемент 45 Неаырождеинзя матрица 87 Независимые (непересекающвеся) циклы 54 Нейтральный элемент 139 Неопределенная линейная система 21 Неподэижизл притягивающая точка 263 — точка 263 Неприэодимьй миогочлен 190, 197 Неравенство Коши — Буняковского — Шварца 176 Несобственный делитель 61 Нечетная перестановка 57 Нижняя треугольная матраца 25 Норма числа в квадратичном поле 176 Нормализованный (нормвроэанвый, унитарный) многочлен 188 Нормальная фундаментальная система решений 198 Область значений отображения 35 — определения отображения 35 Обобщенная ассоциативность 136 Обраткмзл матрица 87 Обратимый элемент кольца 158 — — моноида 138 Обратная матрица 87 Обратное отображение 38 Общий закон дистрибутвввости 154 Объединение множеств 34 Ограниченная стрелка 36 Однородный многочлен 187 Одиочлев (моком) 187 Окавмлюощвй минор 126 Предметнмб указашель 269 Оператор дифференцирования 213 — частного дифференцирования 219 Определенная линейная система 21 Определитель Вандермовда 115 — матрицы 29, 104 — провзведеюш матриц 118 — с углом нулей 117 Орбита 53 Орвевтврованный объем 103 Основная теорема алгебры 233 — — арифметики 62 Основные свойства определктеля 107, 112 Отделение корней (нулей) много- члена 244 Отношение эквивалентности 41 Отобра1кевве 35 — биектнввое 36 — внъектнввое 36 — сюръектвввое 36 Пересечение множеств 34 Перестановка 51 Плоскость комплексных чисел 169 Подгруппа 140 Подкольцо 152 Подмножество 34 †, замкнутое относительно операции 136 Подполе 160 Подстановка в многочлен 184 Поле 159 — Галуа 163 — комплексных чисел 169 — отношений (частных, дробей) 202 Поле разложенвя многочлена 237 — рациональных дробей 203 Полнлнневная функция 105 Полнномиальная фувкцня 210 Полная линейная группа 139, 140 — степень мвогочлева 186 Полное матричное кольцо 153 Положительная марковская матрица 99 Полугруппа 135 Порядок на множестве 44 — перестановки 53 — степенного ряда 189 Порядок элемента 142 Постоянная функция 153 Постоянное отображение 38 Поточечнья операция 153 Праввло знаков Декарта 249 Праанльная дробь 204 Представитель класса 41 Приведенная линейная система 20 Признав делимости 194 Прнмарная дробь 206 Прнмвтнввьш (первообрзэный) корень вз единицы 174 — многочлен 198 Принцип двойной индукции 50 — индукции 46 Присоединенная (взаимная) матрица 121 Проблема якоована 260 Произведение матрвц 82 Произведение (композвцвя) отображений 37 Производная многочлена 212 Производящая функция 189 Простейшая дробь 204 Простое поле 162 Простой корень 209 — элемент кольца 190 Пространство решений 96 — столбцов (строк) прямоугольвон матрицы 74 Прямоугольная матраца 20 Пустое множество 34 Разложение определителя 113 Размерность линейной оболочки 71 Разность множеств 34 Ранг матрицы 75 — — по столбцам (по строкам) 74 — произведения матриц 84 — системы векторов 71 Расширение пола 160 Расширенная матрица линейной системы 21 Рациональная функция 212 Редуцированный мвогочлев 210, 218 Результант 229 270 Предметпныб укаэашель Рефлекснзность 41 Решение линейной системы 21 Свободные неизвестные 24 Свободный член уравнения 20 Символ Кронекера 86 Симметрическая группа 52 — разность множеств 40 — функция 217 Симметрический многочлен 220 Симметричность 41 Система линейных уравнений 19 — (ряд) Штурма 245 Скалярная матрица 20, 86 Собственное подмножество 34 Совместная линейная система 21, 77 Содержание многочлена 198 Специальная линейная группа 140 Сравнение 155 Срезанная экспонента 248 Стандартная система Штурма 247 Стандартный базис 70 Старший коэффициент 186 Степенная сумма 224 Степень многочлена 286 — элемента 137 Столбец матрицы 20 — определителя 105 Строка матрицы 20 — определителя 105 Ступенчатый вид линейной системы 24 — — матрицы 24 Суперпозиция отображений 37, 153 Схема Горнера 208 Сюръективиое отображение 36 Табмена Кэпи 144 Тело 159 Теорема Безу 208 — Бюдана — Фурье 251 — Вильсона 218 — Кровекера — Капелли 77 — Кэпи 146 — Руше 253 — Ферма (малая) 161 Теорема Шевалле 218 — Штейиица 233 — Штурма 245 Тождество Эйлера 219 Травзитивиость 41 Транспозвция 55 Транспонированная матрица 83 Трансцендентный элемент 184 Треугольная диаграмма 37 — матрица 25 Тригонометрическая форма комплексного числа 171 'Универсальное свойство кольца многочленов 184 Уиимодулярнея группа 140 Упорядочение множества 44 Устойчивый многочлеи 251 Факториальиое кольцо 190, 197 Факторизация отображений 43 Фактормножество 42 Форма 187 Формальный степешюй ряд 188 Формула (интерполяционная) Лагранжа 211 Формула Лагранжа 243 — Лейбввца 213 — Муавра Г73 — (интерцоляциоинал) Ньютона 211 — "полного развертывания" 104 — Стирливга 60 — Тейлора 251, 257 — Эйлера 173 Формулы Виета 217 — Крамера 123 — Ньютона 225 Фундаментальная система решенвй 98 Функцвя 35 — Эйлера 64 Характеристика пола 161 Предметный указатель 271 Целая рациональная функция 210 Целостное кольцо 158 Цепь 44 Цикл 53 Циклическая группа 142, 145 'Частичный порядок 44 Частное 159 — дифференцирование 219 — от деления 63, 188 Четверная группа 151 Четнал перестановка 57 Число перемен знаков 245 — Ферма 47 — Фибоиаччи 27 Чисто мнимое число 169 Эквивалентность линейных систем 22 Эквивалентные матрицы 92 Элемент кольца яильпотентный 165 — множества 33 Элементарные матрицы 91 — преобразования 21, 74 — симметрические многочлены 221 Эндоморфизм алгебры многочлеиов 259 Эпиморфкзм 148, 157 Ядро гомоморфизма 147, 156 — линейного отображения 97 Якобиан 259 Учебное пособие КОСТРИКИН Алексей Иванович ВВЕДЕНИЕ В АЛГЕВР'У Часть 1 ОСНОВЫ АЛГЕБРЫ Редактор Ж.Ю.
Ходом Оригинал-макет Н.Н. Андреева ПР .че 071930 от 06.07 99 Подписано в печать 05 12 99 Формат 60х90, гв Бумага офсетная .'4 1. Печать офсетная. Уел псч. л. 17. Уч -пзд. л. 18,7 Тираж 3000 з Издательская фирма "Физико-математичсска МАИК "Наука,'Интерпсриодика 117864 Москва, ул. Профсоюзная, Отпечатано с оригинал-макета в Чебоксарской т 428019,г. Чебоксары, пр. И. Яковлева, 15 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
