Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 177
Текст из файла (страница 177)
28-2. Сплайны Один из практических методов интерполяции набора точек при помощи кривых заключается в использовании кубических силайлов (сиЬ1с зр1шез). Пусть задан набор ((х;, у,): г = О, 1,..., и) из и+ 1 точек, причем хо < хт « х„. Мы хотим провести через эти точки кусочно- кубическую кривую (сплайн) 1"(х). Кривая Г"(х) состоит из и кубических полиномов Л (х) = сн + Ь,х + с,хз + а;хз (г = О, 1,..., и — 1).
Когда х находится в диапазоне х; < х < хсьы значение кривой вычисляется как г' (х) = й (х — х;). Точки х;, в которых состыковываются кубические полиномы, называются узлами (кпо1з). Для простоты будем считать, что х; = г при з = 0,1,...,и — 1. Чтобы обеспечить непрерывность ~ (х), потребуем выполнения условий Дх;) = ЯО) = у;, Дх+з) = Я1) = у+з для г = О, 1,..., и — 1. Чтобы функция г" (х) была достаточно гладкой, мы также потребуем непрерывности первой производной в узлах: г"'(хз+т) = Я (1) = Д з (0) для г = 0,1,...,и — 1. а) Предположим„что нам даны не только пары ((х;, у;)), но и значения первых производных Р; = г'(х,) в каждой точке з' = 0,1,...,и.
Выразите коэффициенты ан Ь,, с; и а; через у;, у;+м Рз и Рвьз (напомним, что х; = г). Сколько времени потребуется для вычисления 4и коэффициентов при таких условиях? Глава 28. Работа с матрицами 867 Остается вопрос о вычислении первой производной 7"(х) в узлах. Один из методов их определения состоит в том, чтобы обеспечить непрерыв- ность второй производной в узлах, так что 7"" (х;+1) = Я'(1) = Я+1 (0) для ( = О, 1,..., и — 1.
Мы полагаем, что в первом и последнем узлах У (хо) = У~о'(0) = 0 и У» (х„) = У„" 1(1) = О. Это предположение дает нам естественный кубический снлайн (па1ига! сиЬ!с зр11пе). б) Используя непрерывность второй производной, покажите, что для к=1,2,...,п — 1 Р1 1+ 4Р, + Р;+1 = 3 (уьы — у; 1) . (28.35) в) Покажите, что 2Ро + Р1 —— 3 (у1 — уо), Р„1 + 2.0„= 3 (у„— у„~ ) . (28.36) (28.37) г) Перепишите уравнения (28.35)-(28.37) в матричном виде с использованием вектора неизвестных Р = (Ро, Ры..., Р„). Какими свойствами обладает матрица вашего уравнения? д) Докажите, что множество из п+1 точек может быть интерполировано при помощи естественного кубического сплайна за время О (и) (см.
задачу 28-1). е) Покажите, как построить естественный кубический сплайн, который интерполирует множество из п+ 1 точек (х,, у,), где хо < х1 < « х„и х; не обязательно равны г. Какое матричное уравнение надо для этого решить и сколько времени для этого потребуется? Заключительные замечания Имеется множество превосходных работ, в которых вопросы числовых и научных вычислений рассматриваются существенно более детально, чем в данной книге можем позволить себе мы. В особенности хочется порекомендовать следующие книги: Джордж (Оеогйе) и Лью (1.ш) [113), Голуб (Оо!иЬ) и ван Лоан (Чап 1.оап) [125), Пресс (Ргезз), Фланнери (г!аппегу), Тукольски (Теи!со!з)су) и Веттерлинг (Чепег!!л8) [248, 249), Стренг (Б!гап8) [285, 286). В книге Голуба и ван Лоана [125) рассматриваются вопросы численной устойчивости.
Они показали, почему сает (А) не может служить хорошим показателем устойчивости матрицы А, предложив вместо него использовать величину 868 Часть ЧП. Избранные темы '8А() '8А 1'8, где 8А)) = шахг<,<„,'~;" )аО). Кроме того, они рассмотрели также вопрос вычисления указанного значения без реального вычисления обратной матрицы А г.
Публикация алгоритма Штрассена в 1969 году [287] произвела сенсацию — до этого было трудно даже представить, что обычный алгоритм умножения матриц может быть улучшен. С того времени асимптотическая верхняя граница сложности умножения матриц была существенно улучшена. Асимптотически наиболее эффективный алгоритм умножения матриц размером и х п приведен в работе Копперсмита (Соррегзш11п) н Винограда (%1пойгас1) [70] и имеет время работы О (пз з~а). Графическое представление алгоритма Штрассена приведено в работе Патерсона (Ра1егзоп) [238].
Метод исключения неизвестных Гаусса, на котором основаны алгоритмы 1Л- и 1Л)Р-разложения, был первым систематическим методом решения систем линейных уравнений, и одним из первых численных алгоритмов. Хотя он был известен и ранее, его открытие обычно приписывают К. Ф. Гауссу (С. К Оацзз) (1777-1855).
В своей знаменитой работе [287] Штрассен также показал, что матрица размером и х п может быть обращена за время О (и'Я т). Виноград [317] доказал, что умножение матриц не сложнее обращения, а обратная оценка была получена Ахо (АЬо), Хопкрофтом (Норсгой) и Ульманом (()11шап) [5]. Еще одним важным разложением матриц является сиигуллрное разложение (гйпйи1аг ча!ие десошроз111оп, БУП). ЯУ13-разложение матрицы А размером т х и представляет собой разложение А = ЯгЕ Я~э, где Г.
— матрица размером т х и, в которой ненулевые элементы находятся только на диагонали, Яг — матрица размером т х гп со взаимно ортонормальными столбцами, а матрица Яз имеет размер п х п и также обладает свойством взаимной ортонормальности столбцов. Два вектора называются ортонормальнымн (опЬопоппа1), если их скалярное произведение равно О, а норма каждого вектора равна 1. Сингулярное разложение хорошо изложено в книгах Стренга [285, 286] и Голуба и ван Лоана [125]. Прекрасное изложение теории симметричных положительно определенных матриц (и линейной алгебры вообще) содержит книга Стренга [286].
ГЛАВА 29 Линейное программирование Многие задачи можно сформулировать как задачи максимизации или минимизации некой цели в условиях ограниченности ресурсов и наличия конкурирующих ограничений. Если удастся задать цель в виде линейной функции нескольких переменных и сформулировать ограничения в виде равенств или неравенств, связывающих эти переменные, мы получим задачу линейного программирования (11пеаг-ргойтапнп1пд ргоЫеш). Задачи линейного программирования часто встречаются в разнообразных практических приложениях.
Начнем их изучение на примере выработки предвыборной политики. Политическая задача Представьте себя на месте политика, стремящегося выиграть выборы. В вашем избирательном округе есть районы трех типов — городские, пригородные и сельские. В этих районах зарегистрировано, соответственно, 100000, 200000 и 50000 избирателей.
Чтобы добиться успеха, желательно получить большинство голосов в каждом из трех регионов. Вы — честный человек и никогда не будете давать обещания, в которые сами не верите. Однако вам известно, что определенные пункты программы могут помочь завоевать голоса определенных групп избирателей. Основными пунктами программы являются строительство дорог, контроль за использованием огнестрельного оружия, сельскохозяйственные субсидии и налог на бензин, направляемый на улучшение работы общественного транспорта.
Согласно исследованиям вашего предвыборного штаба, можно оценить, сколько голосов будет приобретено или потеряно в каждой группе избирателей, если потратить 1 000 долл. на пропаганду по каждому пункту программы. Эта информация представлена в табл. 29.1. Каждый элемент данной таблицы 870 Часть Ч11. Избранные темы показывает, сколько тысяч избирателей из городских, пригородных или сельских районов удастся привлечь, потратив 1 000 долл. на агитацию в поддержку определенного пункта предвыборной программы.
Отрицательные элементы отражают потерю голосов. Задача состоит в минимизации суммы, которая позволит завоевать 50000 голосов горожан, 100000 голосов избирателей из пригородных зои и 25 000 голосов сельских жителей. Таблица 29.1. Влияние предвыборной политики на настроения избирателей Методом проб и ошибок можно выработать стратегию, которая позволит получить необходимое количество голосов, но затраты на такую стратегию могут оказаться не самыми низкими. Например, можно выделить 20 000 долл. на пропаганду строительства дорог, 0 долл. на агитацию в пользу контроля за использованием оружия„4 000 долл.
на пропаганду сельскохозяйственных субсидий и 9 000 долл. на агитацию за введение налога на бензин. При этом удастся привлечь 20. (-2) + +О. (8)+4 (0)+9.10 = 50 тысяч голосов горожан, 20. (5)+0-(2)+4 (0)+9. 0 = 100тысячголосовжителейпригородови 20 (3)+О ( — 5)+4 10+9 ( — 2) = = 82 тысячи голосов сельских жителей. Таким образом, будет получено ровно необходимое количество голосов в городских и пригородных районах и большее количество голосов в сельской местности. (Получается, что в сельской местности привлечено голосов больше, чем наличное число избирателей!) Чтобы получить эти голоса, придется потратить на пропаганду 20+0+4+9 = 33 тысячи долларов. Возникает естественный вопрос: является ли данная стратегия наилучшей из возможных, т.е.
можно ли достичь поставленных целей, потратив на пропаганду меньше денег? Ответ на этот вопрос можно получить, действуя методом проб и ошибок, однако вместо этого хотелось бы иметь некий систематический метод для ответа на подобные вопросы. Сформулируем данный вопрос математически. Введем 4 переменные: ° хз — сумма (в тысячах долларов), потраченная на пропаганду программы строительства дорог, ° хз — сумма (в тысячах долларов), потраченная на агитацию в пользу кон- троля за использованием оружия, ° хз — сумма (в тысячах долларов), потраченная на пропаганду программы сельскохозяйственных субсидий, 871 ° х4 — сумма (в тысячах долларов), потраченная на агитацию за введение налога на бензин. Требование получить не менее 50000 голосов избирателей-горожан можно запи- сать в виде неравенства — 2х1 + 8хз + Охз + 10х4 ) 50. (29.1) Аналогично, требования получить не менее 100000 голосов избирателей, жи- вущих в пригороде, и 25 000 голосов избирателей в сельской местности можно записать как неравенства 5х1 + 2хз + Охз + ОХ4 > 100 (29.2) Зх1 — 5хз+ 10хз — 2х4 ) 25.
(29.3) Любые значения переменных х1, хз, хз, х4, удовлетворяющие неравенствам (29.1)-(29.3), позволят получить достаточное количество голосов избирателей в каждом регионе. Чтобы сделать затраты минимально возможными, необходимо минимизировать сумму, затраченную на пропаганду, т.е. минимизировать выра- жение (29.4) Х1 + Х2 + Хз + Х4. Хотя отрицательная агитация часто встречается в политической борьбе, отрица- тельных затрат на пропаганду не бывает. Поэтому следует записать условия Х1 )~ О, Х2 )~ О, хз ~ )0 и х4 ~ )О. (29.5) Поставив задачу минимизации выражения (29.4) при соблюдении неравенств (29.1К29.3) и (29.5), мы получаем так называемую "задачу линейного програм- мирования*'.
Запишем ее следующим образом: (29.6) Минимизировать х1+ хз+ прн условиях ХЗ + Х4 х1~ Х2з ха~ х4 > О Решение данной задачи линейного программирования позволит политику полу- чить оптимальную стратегию предвыборной агитации. Глава 29.
Линейное программирование — 2х1+ 8хз+ Охз+ 10х4 > 50 5Х1 + 2хз + Охз + Ох4 > 100 Зх1 — 5хз + 10хз — 2х4 > 25 (29.7) (29.8) (29.9) (29.10) Часть Чй. Избранные темы 872 Общий вид задач линейного программирования В общем случае в задаче линейного программирования требуется оптимизировать некую линейную функцию при условии выполнения множества линейных неравенств. Для данных действительных чисел аы аз,..., а„, и множества переменных хы хз,..., х„линейная функция этих переменных Г" определяется как ~(хыхз,...,х„) =а1х1+азхз+ а„х„= ~> а~х . г=1 Если 6 — действительное число, а г" — линейная функция, то выражение г (хз хз> .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
