Бабенко - Основы численного анализа (947491), страница 13
Текст из файла (страница 13)
матриц, для которых не возникнет препятствия при обратценпи промежуточных матриц), образует от- 2 крытое множество в В." . Поэтому имеются основания считать, что метод исключения Гаусса не оптимален. Алгоритм 111трассена основан на том факте., что умножение двух 2 х 2-матриц в некоммутативном кольцо можно выполнить, используя лшпь семь умножений. Если бы число Глава 1.
Постановка задач чавлвнивго анализа умножений можно было уменьшить, то мы сразу бы получили более экономный алгоритм умножения и х п-матриц. Однако можно показать, что число умножений уменьшить нельзя [7]. Тем не менее алгоритм Штрассена первый в ряду алгоритмов, в которых последовательно понижалось число операций при умножении матриц.
Последняя оценка 0(па) (о = 2,376) для числа операций, необходимых для умножения двух матриц размером и х и, приведена в (187, 151., 98). Много лет в математическом фольклоре бытует следующая Гипотеза, Обращение матрицы порядка п,,мешено выполнить за О(п~ а) операций, где. е > 0 — произвольно малое число. Указанный результат явно говорит в пользу этой гипотезы.
Однако практическая ценность подобных оптимальных методов пока совер|пенно неясна, и возможно, что положительный ответ на поставленный вопрос мало нас продвинет вперед в деле решения систем линейных уравнений. Говоря о временной сложности тех или иных аагоритыов, мы неявно предполагали, что вычисления производятся последовательно, и не касались вопроса о пара;пельных вычислениях.
Параллельные вычисления зто особая тема, и мы из-за недостатка места ее не касаемся. Отметим только, что учет параллельности приводит к резкому изменению наших взглядов на оптимальность некоторых алгоритмов. Это еще одна из причин, почему мы ограничили число рассматриваемых алгоритмов в задачах линейной алгебры. Глдвд 2 Математические основы численного анализа В з 1 этой главы приводятся иекоторые факты топологии и функционального анализа, а в Я2-4 факты математического анализа, иа которые будем опираться в дальнейшем. ~ 1.
Теоремы топологии и функционального анализа 1. Компакты и их свойства. При обсуждении топологических вопросов ограничимся рассмотреиием метрических прострапств. Пусть ~С, р) — метрическое пространство, где С вЂ” миожество его элементов, р расстояние. В дальнейшем это метрическое пространство будем обозиачать >>роста символом С. Система множеств 1Х ) (Х е С) называется попре>тием пространства С, если и О Хь =- С.
Покрытие, состоящее из открытых (залгкиутых) множеств, иазывается открыт м (замкну>пь>м) покрытием. Метрическое просэранство иазыввтся компактнымэ еггпэ любое его открытое покрытие содержит конечное лодпокрытие. Компактное метрическое просграиство будем навеивать ме>приэесхим компактом или просто компактом.
Перечислим некоторые свойства компактиых пространств )61): 1) если С вЂ” компактное пространство, то каждое его бесконечное подмио>кество имеет хотя бы одну предельную точку; 2) замкнутое подмножество компактного пространства компактно, 3) компакт замкнут в любом содержащем его полком метрическом простраистве, Если Х, г' — множества, то запись 1: Х г' обозиачэет отображение Х в У. Образ множества Я С Х обозначим через 1"121: обратный образ, или полный прообраз множества И' С У, обозначим через >" '1И'). Стало быть, УЮ = У( ) 6 Х), У '1Иг) =- )х: У(х) Е И') Отображение называется инэехгглиеным., если Дх>) Л 1'Лхг) для любых аг, хг Е Х., х> И хг, и е>орэехтиенхям, если )'1Х) .— — У.
Рассмотрим непрерывные отображения компактов. Пусть С колплакт, Н вЂ” метрическое пространство и р: С э Н непрерывное отображение. Теорема 1 )61, с. 1!8). Непрерь>ень>й образ компакта — компакт. Эта теорема -- цепосредствепиое счедствие >ого, что при иепрерывиом отображении прообразы открытых множеств открыты. При Н = В. получается отображение коьшакта в числовую прямую; лля этих функций сохраняются свойства, справедливые для непрерывных функций иа отрезке; Теорема 2.
Пусть С вЂ” компакт, ум С В. — непрерывное отображение. Тогда р ограничено на компакте С и достигает на нем верхней и нижней граней. 56 Глава 2. Математические основы числсннога апалиоа Доклзлткльство. В силу теоремы 1 р(С) — компактное подмножество Й., т. е. оно ограничено и замкнуто, а значит, содержит конечные верхнюю и нижнюю грани. П Проверка того, что данное подмножество метрического пространства является компактом, на основе приведенного определения компактности затруднительна.
Для подмножеств метрических пространств можно указать иное свойство, эквивалентное компактности. Это свойство легче проверить. Пусть Х подмножество метрического просгрансгва С. Диаметрам этого подмяожества будем называть величину д'Х; =-- зир р(х, у). Если х — про.,гсх извольная точка С, то расстоянием х от подмножества Х назовем величину б(х, Х) —.. 'шЕ р(х, у). гех Множество У П С называется =--сетью для Х, если для любого элемента х б Х существует такой элемент р б У, что р(х, у) < =". Множество У может и не содерхсаз ься в Х и даже иметь с Х пугтое пересечение, однако если для Х существует е-сетгь то существует 2е-сетгь востокогаз из точек множества Л.
Множество Х С С называется вполне ограниченньсм, если для любого " > О оно имеет конечную г-сеть. Ясно, что вполне ограниченное множество будет и ограниченным. Если множество Х вполне ограничено, то и его замыкание Х будет также вполне ограниченным. (Условиьсся в дальнейшем замыкание множества обозначать чертой сверху символа, обозначающего данное множество.) Теорема 3. Длл того, чтобъс метрическое врастраостла С было компакглам, необ~одима и досглаточно, чтобы оно было вполне аграниченннм и валким [61, с. 127).
Если множество Л' с С не замкнуто в С, го оно пе может быть компактом. Однако бывают случаи (и читатель может сам привести тому многочисленные примеры), когда замыкание Х множества Х у.же компакт (например, любое открытое ограниченное эпю>кество в л-мерном пространстве Н"). Множество Х О С называется предкампактным, если его замыкшсие в С компактно. Множество Х С С называется ограниченно комвакслньсм, если любое его замкнутое ограниченное подмножество компактно.
2. Компакты в линейных нормированных пространствах. Для компактов, лежащих в линейных нормированных пространствах, можно указать еще одно их характеристическое свойство, удобное в приложениях к численному анализу. Пусть Х вЂ” некоторое подмножество метрического пространства С. Покрытие 1Х„) множества Х называется е-гсокрьсглием, если вор д[Х,„) < г. Допустим, что мы имеем некоторое непрерывное отображение р: Х с С. Отображение р называется е-отабрахсением, если для любой точки р б б сг(Х) С С найдетсЯ такаЯ окРестность ссг С С, что с1[сР '[Сц б;Р1Х))] < г.
Отображение р называется е-сдвигом, если для любого элемента х Е Х имеет ъсесто неравенство р(х. ср(х)) < е. Ниже мы оудом рассматривать подмножества линейного нормированного пространства В. Норму в нем обозначим через [ Теорема 4. Если длл ограниченного множества Х ври любом г > О существует с--сдвиг в коне чномгрное падпрастранство 1,"', та Х вполне огра- З 1.
Теорсмь! и!апологии и функц!зонального анализа ничено. Даобороеу если Х вЂ” компакт, гло длл любого . > О сущеспыуега в-сдвиг Х в конечномерное подпроспьранство. Доклзлткльство. 11усть ум Х вЂ” ! Ь~' — в-сдвиг в конечномерное пространство размерности и,, Так как Х -- ограниченное множество, то !р(Х) — тоже ограниченное множество в Ь"'! т.е. для него существует конечная в-сеть У С !р(Х). Пусть элементы этой -сети суть у, 0 = 1, 2, ....
Ж). В каждом из множеств !р '(у,) выберем некоторую точку х, 0 = 1, 2, ..., Л1). Множество (а )!' ! образует Зг-сеть для Х, В самом деле, пусть х б Х, у = =.- Р(х) и уь — ближайгвая к у точка -сети У. Поскольку х — хь †..х — !р(х)-~ у — уь .1 эо(хь) — ты то по неравенству треугольника и из определения -сдвига получим ) х — хь'! ( '(х — р(х)( —, ( у — уь( -~- !' о(!гь) — хь)! ( (Зг. Построена в-сеть для Л. Первая часть теоремы доказана. Докавгем вторую часть теоремы. Если Х компакт, то для любого г > О существует конечное открытое г-покрытие (Л! Ц !. В каждом из элементов покрытия Хь выберем некотору!о точку х! (ь. = 1, 2,..., п).
Рассмотрим разбиение единицы, определяемое покрытием (Хь)'„',. Положим Ль(х) = о(х, Х 1, Хь)/~ 6(х, Х 1 Х;). г=. ! 51сио, что О ( Ль(х) ( 1, 2 Ль(т) = 1. Покажем, что Лг(х) — непрерывные ь=! функции. Непрерывность О(х, Х !! Хь) очевидна. Поэтому 2 б(х, Х !, Х,) г=! непрерывная функция, и по теореме 2 она достигает своей нижней грани. Допустим, что .па нижняя грань равна нулю. Тогда найдется точка хо б Х, для которой 2 б(хо, Х !! Х,) = О.
откуда следует, что хо Ф Х„при ! = 1, 2,..., и. г=! Следовательно, то р' 0 Х! =- Л, что неверно. Таким образом, эта нижняя грань положительна, и, следовательно, функции Ль(х) непрерывны. Выберем в каждом жгементе покрьн ия Хг по некоторой точке хь (й = 1, 2,... ! п) и рассмотрим функцию х(х) = ~ Ль(х)хы ь=! Ясно, что р: Х В вЂ” непрерывное отображение. Если Лг(х) ~ О, то х б б Хь! пусть для произвольного элемента х б Х элементы Хь, () = 1, 2, ..., т) те элементы в-накрытия, которые содержат точку х. Тогда го ю р( )= у Л„,(х): з, ~ Л,(х)=1. ! :.. ! г=! и, следовательно, р(х) . х = ~ Льг(х)(хь, х) г=! 58 Глава 2. Магг!ематические основы численного аналиоа откуда но неравенству треугольника !!р(х) — х(~ (~ Ль,(х) )хг, — х;! ~ (е ~ Л»,(х) = е.
э=! э.—:! На векторы хь (1« = 1, 2,..., и) натянем линейное надпространство Е минимальной размерности. Поэтому р — е-сдвиг в А — в конечномерное надпространство. П Злмгчлннн, Сходным методом может быть получена теорема Аггександрова об е-сдвиге компакта в некоторый нолиэдр. Закончим этот раздел доказательством простой, но важной теоремы. В банаховом пространстве В нодмпожество Т(х„, е) = (х!:1х — хо~ ( е1 будем называть итром радиуса е с централ«е хо. Теорема б.
Если замыкание единичного шара Т(0, 1) банахоеа пространства  — компактное мнооюестео, то пространство В конечномерно. Доклзлтнльство. По теореме 3 для лшожества Т(0, 1) существует конечная 11'2-сеть тэ,, х,„. Таким образом, Т(0, 1) С Ц Т(хэ, 112). Натянем на векторы хэ, ..., х надпространство П Последнгою формулу можно переписать в виде Т(О, Ц с 1. —, Т(О, 112). где последнюю сумму нужно понимать как множество элементов вида ел у ! х б Б 1, р б Т(0, 112). Поскавьку при Л > 0 имеем Л1 =- 1, Л'Г(0, 1) = Т(0, Л), то Т(0, 1э!2) С Ь+ Т(0, 1э!2г), откУда Т(0, 1) С Ь+ Е+ Т(0, 112з) = Ь+ Т(0, 112!).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
