Читаем Программирование. Принципы и практика использования C++ Исправленное издание полностью

Если вы умеете работать с двумерными объектами класса Matrix, то сможете работать и с трехмерными. Например, здесь a — трехмерная матрица, поэтому a[i] — двумерная (при условии, что индекс i не выходит за пределы допустимого диапазона); a[i][j] — одномерная (при условии, что индекс j не выходит за пределы допустимого диапазона); a[i][j][k] — элемент типа int (при условии, что индекс k не выходит за пределы допустимого диапазона).

Поскольку мы видим трехмерный мир, при моделировании чаще используются трехмерные объекты класса Matrix (например, в физическом моделировании в декартовой системе координат).

int grid_nx; // разрешение сетки; задается вначале

int grid_ny;

int grid_nz;

Matrix cube(grid_nx, grid_ny, grid_nz);

Если добавить время в качестве четвертого измерения, то получим четырехмерное пространство, в котором необходимы четырехмерные объекты класса Matrix. И так далее. 

<p id="AutBody_Root472"><strong>24.6. Пример: решение систем линейных уравнений</strong></p>

  Если вы знаете, какие математические вычисления выражает программа для численных расчетов, то она имеет смысл, а если нет, то код кажется бессмысленным. Если вы знаете основы линейной алгебры, то приведенный ниже пример покажется вам простым; если же нет, то просто полюбуйтесь, как решение из учебника воплощается в программе с минимальной перефразировкой.

Данный пример выбран для того, чтобы продемонстрировать реалистичное и важное использование класса Matrix. Мы решим систему линейных уравнений следующего вида:

a1,1x1 + ... + a1,nxn = b1

...

an,1x1 + ... + an,nxn = bn

где буквы x обозначают n неизвестных, а буквы a и b — константы. Для простоты предполагаем, что неизвестные и константы являются числами с плавающей точкой.

Наша цель — найти неизвестные, которые одновременно удовлетворяют указанные n уравнений. Эти уравнения можно компактно выразить с помощью матрицы и двух векторов.

Ax = b

где A — квадратная матрица nxn коэффициентов:

Векторы x и b векторы неизвестных и константа соответственно.

В зависимости от матрицы A и вектора b эта система может не иметь ни одного решения, одно решение или бесконечно много решений. Существует много разных методов решения линейных систем. Мы используем классическую схему, которая называется исключением Гаусса. Сначала мы преобразовываем матрицу A и вектор b, так что матрица А становится верхней треугольной, т.е. все элементы ниже диагонали равны нулю. Иначе говоря, система выглядит так.

Алгоритм несложен. Для того чтобы элемент в позиции (i,j) стал равным нулю, необходимо умножить строку i на константу, чтобы элемент в позиции (i,j) стал равным другому элементу в столбце j, например a(k, j). После этого просто вычтем одно уравнение из другого и получим a(i,j)==0. При этом все остальные значения в строке i изменятся соответственно.

Если все диагональные элементы окажутся ненулевыми, то система имеет единственное решение, которое можно найти в ходе обратной подстановки. Сначала решим последнее уравнение (это просто).

an,nxn = bn

Очевидно, что x[n] равен b[n]/a(n,n). Теперь исключим строку n из системы, найдем значение x[n–1] и будем продолжать процесс, пока не вычислим значение x[1].

При каждом значении n выполняем деление на a(n,n), поэтому диагональные значения должны быть ненулевыми. Если это условие не выполняется, то обратная подстановка завершится неудачей. Это значит, что система либо не имеет решения, либо имеет бесконечно много решений. 

<p id="AutBody_Root473"><strong>24.6.1. Классическое исключение Гаусса</strong></p>

Посмотрим теперь, как этот алгоритм выражается в виде кода на языке С++. Во-первых, упростим обозначения, введя удобные имена для двух типов матриц, которые собираемся использовать.

typedef Numeric_lib::Matrix Matrix;

typedef Numeric_lib::Matrix Vector;

Затем выразим сам алгоритм.

Vector classical_gaussian_elimination(Matrix A,Vector b)

{

  classical_elimination(A, b);

  return back_substitution(A, b);

}

Иначе говоря, мы создаем копии входных матрицы A и вектора b (используя механизм передачи аргументов по значению), вызываем функцию для решения системы, а затем вычисляем результат с помощью обратной подстановки. Такое разделение задачи на части и система обозначений приняты во всех учебниках. Для того чтобы завершить программу, мы должны реализовать функции classical_elimination и back_substitution. Решение также можно найти в учебнике.

void classical_elimination(Matrix& A,Vector& b)

{

  const Index n = A.dim1;

  // проходим от первого столбца до последнего,

Перейти на страницу:

Похожие книги

97 этюдов для архитекторов программных систем
97 этюдов для архитекторов программных систем

Успешная карьера архитектора программного обеспечения требует хорошего владения как технической, так и деловой сторонами вопросов, связанных с проектированием архитектуры. В этой необычной книге ведущие архитекторы ПО со всего света обсуждают важные принципы разработки, выходящие далеко за пределы чисто технических вопросов.?Архитектор ПО выполняет роль посредника между командой разработчиков и бизнес-руководством компании, поэтому чтобы добиться успеха в этой профессии, необходимо не только овладеть различными технологиями, но и обеспечить работу над проектом в соответствии с бизнес-целями. В книге более 50 архитекторов рассказывают о том, что считают самым важным в своей работе, дают советы, как организовать общение с другими участниками проекта, как снизить сложность архитектуры, как оказывать поддержку разработчикам. Они щедро делятся множеством полезных идей и приемов, которые вынесли из своего многолетнего опыта. Авторы надеются, что книга станет источником вдохновения и руководством к действию для многих профессиональных программистов.

Билл де Ора , Майкл Хайгард , Нил Форд

Программирование, программы, базы данных / Базы данных / Программирование / Книги по IT
Программирование. Принципы и практика использования C++ Исправленное издание
Программирование. Принципы и практика использования C++ Исправленное издание

Специальное издание самой читаемой и содержащей наиболее достоверные сведения книги по C++. Книга написана Бьярне Страуструпом — автором языка программирования C++ — и является каноническим изложением возможностей этого языка. Помимо подробного описания собственно языка, на страницах книги вы найдете доказавшие свою эффективность подходы к решению разнообразных задач проектирования и программирования. Многочисленные примеры демонстрируют как хороший стиль программирования на С-совместимом ядре C++, так и современный -ориентированный подход к созданию программных продуктов. Третье издание бестселлера было существенно переработано автором. Результатом этой переработки стала большая доступность книги для новичков. В то же время, текст обогатился сведениями и методиками программирования, которые могут оказаться полезными даже для многоопытных специалистов по C++. Не обойдены вниманием и нововведения языка: стандартная библиотека шаблонов (STL), пространства имен (namespaces), механизм идентификации типов во время выполнения (RTTI), явные приведения типов (cast-операторы) и другие. Настоящее специальное издание отличается от третьего добавлением двух новых приложений (посвященных локализации и безопасной обработке исключений средствами стандартной библиотеки), довольно многочисленными уточнениями в остальном тексте, а также исправлением множества опечаток. Книга адресована программистам, использующим в своей повседневной работе C++. Она также будет полезна преподавателям, студентам и всем, кто хочет ознакомиться с описанием языка «из первых рук».

Бьерн Страуструп , Бьёрн Страуструп , Валерий Федорович Альмухаметов , Ирина Сергеевна Козлова

Программирование, программы, базы данных / Базы данных / Программирование / Учебная и научная литература / Образование и наука / Книги по IT