Бабенко - Основы численного анализа (947491), страница 134
Текст из файла (страница 134)
Реализация этой программы бывает непростой и кроме затрат машинного времени требует большого мастерства. Затронутый вопрос самым тесным образом связан с так называемыми доказательными вычислениями в анализе, Пол доказошельиыми вычислениями в анализе мы понимаем такие целенаправленные вычисления на ЭВМ, комбинируемые с аналитическими исследованиями, которые приводят к строгому установлению новых фактов (теорем). Идея использования ЭВМ лля решения не чисто вычислительных задач не нова.
Уже довольно давно стали приспосабливать ЭВМ к получению утверждений в формализованных теориях теоретической математики, например 658 Глава в, >?ислснпас реи>свис краевых задач дчя вывода теорем элементарной геометрии и т. п. Известно, что в настоящее время ЭВМ широко используются для выполнения аналитических преобразований, в прикладной комбинаторике, в теории игр и в вопросах принятия решений, для редактирования текстов и перевода с одного языка на другой.
Область неарифметического использования ЭВМ все расширяется, и трудно переоценить роль ЭВМ в таком важнейшем вопросе научного творчества, как формулировка гипотез и их последующая проверка (с помощью ЭВМ). Особенно продуктивно использование ЭВМ в теории чисел, где очень чагто объект исследования дискретен целое чиешо.
Последнее обстоятельство несколько упрощает проблему достоверности получаемых результатов, хотя она и в этой области довольно с южна. Чтобы бьшо понятно читателю, о чем илет речь, приведем два примера. В качестве гипотезы Л. Эйлер выдвинул утверждение, что уравнение л" + лг + лаз ->- ла — — х,'. не имеет решений в целых положительных числах. С помощью простого перебора на ЭВМ было найдено одно нз решений этого уравнения: л> = 27, хг = 85, хг = 110, ла = 133, ла = 144, чем была опровергнута гипотеза Эйлера.
В данном случае вопрос предельно ясен, .поскольку проверка полученного результата может быть проделана вручную. В последние годы погоня за известным наибольшим простым числом стала очень популярной и высоко престижной областью деятельности, и в ней получены впечатляющие результаты. Хотя простых чисел бесконечное количество, и> казалось бы, идя по ряду натуральных чисел, можно получать все большие и болыпие простые числа и тем самым ставить рекорды, тем не менее прямыми методами не удается зайти сколько-нибудь далеко, так как вычисления становятся практически неосуществимымн.
Поэтому приходится прибегать к и ющренным методам поиска простых чисел. Суптествуют простые числа специального вида, для которых проверка простоты в достаточной к>ере облегчена. К таким простым относятся числа вида 2п — 1, где р — простое чишю. Эти числа в случае их простоты называются прость>ми числами Мсрсснна., и в настоящее время известно около тридцати таких чисел. Проверку числа Мерсенна помогает осуществить следующая 'Георема 1 (Э,.'1укас). Если р > 2 — простое число, то числа 2" — 1 лвллстсл простым тогда и толька тогда, когда Ьр я = О, где Ь, — послсдавательнастгч апре>)еллсмаа рск1>ррснтной формулой Ь, > = (Ьг — 2) шос1 (2>' — 1). С использованием этого теста в 1984 г.
было найдено, что число 2п>гааэ — 1 является простым числом Мерсенна. Это число имеет 39751 цифру, и поэтому нет реальной возможности осуществить ручную проверку полученного результата, :и стало быть, возникает вопрос: сколь он догтоверену Ведь надо исключить погрешности в программе и сбои машины. С этой целью предпринимаются соответствующие проверки. Таким образом, даже в этой ситуации вопрос о достоверности полученных результатов далеко не так прост. Что же касается доказательных вычислений в анализе, то для них указанньш вопрос еще сложнее. 659 з 7.
О даказагпельньех амчвеленилх В рассматриваемой области использования вычислительных машин, граничащей с так называемым искусственным интеллектом, можно нередко столкнуться с поверхностными высказываниями общего характера. А надь лу'ппий способ создать соответствующую теорию это разобрать решение различных и трудных задач и продемонстрировать возможности предлагаемого способа действий. 2. Задача Гаусса. В теории цепных дробей известна проблема, поставленная К.
Гауссом, об агимптотике разности Гп(х) — 1п(1 — х),е 1и 2, где последовательность (Гн(х)) определяется по рекуррентной формуле и=0,1,, Га ив х. Легко доказать, что Г„(х) непрерывно дифференцируема и Г (, ) С Г (1е(й+ ")) (й + х)з и поэтому, полагая ГГ(х — 1е2) = д„(х) (и = О, 1, ...), получим д„1(х) = (Сдп)(х), и = О, 1, ..., где оператор С определен формулой (6.21). Стало быть, д (.) =(Сада)(:), и поэтому асимптотика разности (1) определяется характерами спектра и инвариантцых подпространств оператора С.
Учитывая принеденные выше сведения о спектре оператора С, мы видим, что проблема Гаусса сволится к определению собственного числа, вычислению его кратности и опенке для )Лз,. По нашему мнению, эту программу можно осуществить лишь с помощью вычислений на ЭВМ, но они должны быть доказательными. Мы не можем восщюизводить весь ход вычислений, а расскажем только, как докэзатгь что в круге (Л; Л вЂ” 1ез) < 5 10 и), где пв —.. — 0,3036630028487, лежит хотЯ бы одно собственное значение оператора С. Машинное представление матрицы ал (см. пРимеР 6 З 6) мы обозначим чеРез ед; Гея втоРое собственное значение матрицы ед (порядка 16 х 16).
Отметим, что вычисление матрицы ед было произведено с двойной точяостью, а затем полученные величияы были окрутлены до одинарной точности, так что — < 2 — зэ (2) 660 Глава а. Числвннав решение нраввзмх задач Пусть в' = (Л: /Л вЂ” рз' —— 5 10 ~). Оценим злах ,'(Ж -- Л1) лезз А = Я бз (У Ю Л1) С- 1 (3) и оценим ее норму.
Вначале рассмотрим окружность К и на ней точки Гз .—.... 1зя ч 5 10 а ехр(зззз) (азз =- 2я1зз660, 1 —... О, 1, ..., 659). Вычисляя для этих значений с) матрицу (3), получим, что заведомо (Хл! <39 10 в: Л=ГО; !=0,1,,659 Воспользовавшись формулами (1.1.7)--(1.1.10), мы получим,. что Ул = Ял(У вЂ” Л1) —. 1 = Ул + 5 8608 10 П, (4) (5) где П вЂ”. (ш, )~в~ м пРичем )аз,з < 1. Если тл =. Ял(аза — Л1) — 1, то из неравенств (2), (4) и соотношения (э) вытекает формула ~Ул, < 6,251 10 ', Л.=. Сб 1 =-0 1,, 659 (6) Поскольку Ял =- (Ж вЂ” Л1) "' =- (1 Ч,Чзл)" Ял .=- ~' ( — 1)' РлЯл, =о (7) то !Ял < Ял! (1 — ~~л' ! При Л вЂ”...
~~ (1.—.. О, 1,..., 659) мы подсчитали, что Ял! <1,4 10~, (8) и поэтому для тех же значений Л Ял < 14 000, 01. Если Л ф бь то где ~,'з ближайший к Л узел. Учитывая, что Л вЂ” ~з)'ЯС,(~ < 10 з)ЯС,,зш < 1,400001 < 0,0332, 1320 132 Прелгде всего отметим, что на ЭВМ мы получаем матрицу ( 1 О Л1) = Ял, и поэтому, .чтобы найти матрицу Ял —.. (У вЂ” 1Л) з, нам нужно оценить роль погрешностей округления при вычислении матрицы Ял. Вычислим матрицу 661 ! 7.
0 дакааательимх еычиелеиолх получим Ял < 1.,449 10, Л Е Ж (9) Покажем, что внутри окружности сь лежит собственное значение оператора С. Для этой цели в точках Л .—.. О мы вычислили Ял со,71о, где уо(х) = 7(1,У2-с х) ~ — 12(3/2+ х) . В итоге мы получили, что 13-я компонента вектора Яо С .7 уо при увеличении 1 от 0 до 659 двигалась по часовой стрелке, делая один полный оборот, причем в рассматриваемых точках ,'(Ял 61,7!о)лз~ = 1308,8... Соотношение (7) дает Ял — Ял = ((7+ ~л) ' — !)Ял, откуда ~Ял — Ял~, < ~Ял~ ~Рл !(1 — (~л ), и поэтому из (4) и (8) находим ~Ял — Ял~. <10 ', Ялур — Ял З,7Уо <10 17Уо, '<10': (10) если Л = с5 (1 .— О, 1,, 659). Учитывая эти неравенства и погрепп|ости округления,получим, что при тех же значениях Л 1308 < ~(Ял/Хо)1з( < 1309.
с1тобы получить оценку при произвольном Л 6 'и, воспользуемся тем,что ~Ял — Яс,), <,Л вЂ” сд! Яй "1 — ,'Л вЂ” О) (Я4,(„) ' < 484, где ~~ ближайший узел к Л. Следовательно,. 824 < (Ял /уо)1з < 1793. Л Е 'ь. Отсюда следует, что, когда Л описывает окружность в, точка (Ял1 !о)сз описывает замкнутую кривую, содержащую точку Л = О. В силу последних неравенств и расположения точек (Ял сш,77о)сз при Л (l = О, 1,.... 659) кривая (Л е 'ь: (Ял,у!о)лз) проходится по часовой стрелке так, что производится один полный оборот.
Пусть 77л .=- (С -- Л!) 1 резольвента оператора С. В силу определения оператора 'У ЗС1 -'4д,! = дС(! — Р (.; У)), и если ! 6 В, то по предложению 2 3 6 662 Глава д. Числсннос рсшвшы красвик аадач откуда для произвольного элемента 7 6 В [дСУ вЂ” 'д7Л < Л 1~Л, . Это неравенство ключевое, из него следует соотношение ,,У(С вЂ” ЛЕ)у — (Ю вЂ” Л7),УУ'„~ < гЛ„|[л где Š— единичный оператор. Если Л принадлежит резольвентному мно- жеству оператора С, то, полагая (С вЂ” ЛЕ)7' = д, получим , 'Уд — (у — Л!)Зтслдь < Хь:, :гслд" .
Отсюда для любого элемента д е В !Ял7д — ЛВлй <7Л 0Влд, :!Ял~ " Для того чтобы сформулировать следующее предложение, введем некоторые константы. Пусть Аа константа Лебега интерполяции, д — —. = 1 — 1п(1+ л/2)~[1п(1+ 2о~) — 1п(2ь~ — 1)", о = (к/2 -т- 1) ~1о/2. Имеет место следующее фундаментальное Предложение 1 [13]. Пусгпь Л у эрес С ~,' врес сд, и пусспь 0 < ага(Л) = Аь/ал(1 — б)~7~)Л"7~ — Л„) < ж, где константа б такова, ппо 0 < б < 1, и мооюет быть уточнена в процессе вычислений. Если б ~Ял-<, а(Л) 1„: 1 7к — 3 !)Вл)[„< пгш,, [ + Л), (1 — б) ' ~ь(Л),'Ял), Воспользовавшись этим предложением, положив б = 10 'э, п = 16, Л й 'и', получим гйл~~аь < 2,4 10~, Л й К. (12) Применяя неравенство (11) к функции го при Л Е '4', в силу (12) и очевидного соотношения Ц~г = 7 получим, что ~отелло — Ял Чо,', < 6,4, Л 6 Ж.
Поэтому 13-я компонента вектора дйлуо описывает замкнуту.ю кривую, содержащую точку Л = О, когда Л пробегает окружность Ж, причем зта кривая проходится с изменением ориентации. Таким образом, в круге (Л: 'Л вЂ” уг~ < 5 10 а) лежит по крайней лгере одно собственное значение оператора С. Мы не будем описывать дальнейший ход аналитических выкладок и вычислений: их можно найти в [13[. Отметим, что удается доказать простоту собственного числа Ла и дать оценку для ~Лэ[.
Итак, приходим к следующей теореме 01, З 8. Некоторые ваклтачительнъте ьамечаттттл Теорема 2. Для гауссовской аоследовательностпи (г'„(х)) выполняется ас мтттотическая формула Г„(х) =- ' —: ВЛпт ~д(х) + 0(хр"), х е (О, 1:,. р < 0,15, 1тт(1 — 'х), и 1 1п2 еде д(х) удовлетоорнет услов я.м о(0) = О, ьд(0) = 1, чь'(х) = и'.г(х+1,12), фз(х) — собттптвенная функция оператора С, отвечающая собственному значению Лат Ла = -0,30366300 + д 5-,85 10 е, ,,'д, :< 1; Д=-0,17925+дт 3.,6 10 з,;д~, ,'<1. Аналогичными методами удается изучить спектральную задачу Орра — Зоммерфельда и получить следующий результат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
