Какой алгоритм использовать для решения системы с приведенной матрицей коэффициентов?

Это циклическая трёхдиагональная система ЛУ.

Её можно решить, используя прогонку для чисто трёхдиагональной матрицы и формулу Шермана-Моррисона для модификации решения.

Код можно найти в Numerical Recipes in C, раздел 2.7.2

Как правильно замечено MBo, это циклическая трехдиагональная система линейных уравнений.

Есть несколько вариантов решения:

1. Использование метода прогонки (также, называется алгоритмом Томаса в англоязычной литературе) с последующим применением метода Шермана-Моррисона.

2. Так как ваша матрица симметрична, то можно работать с Cyclic reduction.

3. Преобразование к треугольной системе. Этот дополнительный шаг будет стоить O(N), а дальше все стандартно – ибо треугольные системы решаются тривиально с конца.

4. Использование специализированных алгоритмов для циклических тридиагональных систем. Оригинальная классическая статья: C. Temperton, "Algorithms for the solution of cyclic tridiagonal systems", J. Comp. Phys., vol. 19, no. 3, pp. 317–323, Nov. 1975.

   Хороший обзор дается в отчете M. Piller "On the numerical solution of cyclic tridiagonal systems". В вашем случае, матрица не просто трехдиагональная циклическая, но и с обоими субдиагоналями и "циклическими элементами" равными 1. Тут можно много подэкономить.

Кратко о преимуществах:

Почему использовать прогонку: простое решение и программирование.

Почему использовать другие методы: они более эффективны и могут использовать дополнительные известные свойства матрицы коэффициентов. Также они лучше когда необхоимо решать системы с большим количеством правых частей.

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

Один из простых методов - метод Жордана Гаусса. Даное уравнение решается этим методом https://matworld.ru/calculator/gauss-jordan-method-online.php, лучше применять версию не с сайта, а вариант который без обратного хода. Т.е. первая итерация - вычитание из одной строки другой домноженой на коефициент что бы елемент (1,1) стал равен еденице, и так далее. Единственная особенность этого метода - применение простых дробей. Нужно реализовать операции плюс минус умножить разделить и сократить простую дробь, завернуть этот алгоритм в несколько циклов - и ответ будет максимально точным. После получения еденичной матрицы - ответы можно переводить в десятичные дроби. Я не сравнивал эффективность метода (быстродействие), но для понимания и реализации считаю данный метод относительно не сложным. Я опробывал метод на многих уравнениях - метод вполне рабочий.

Я проверил на указанном сайте - уравнение имеет решение. Метод Жордана-Гаусса всегда решает уравнение за число итераций, которое соответствует степени уравнения. Метод хорошо считается на бумаге, алгоритм хорошо переносится на ПК. Обычно на 1-ом 2-ром втором курсе линейной алгебры оба метода Гауса изучают, а программирование методов идет после, поэтому понимание что делать облегчит задачу.

Недостатки метода Гауса:

• если на ведущей диагонали присутствуют нули, или матрица составлениа так что нет решения для даного метода, то нужно переставлять строки, и искать комбинацию порядка строк такую, что бы не было деление на ноль. Если уравнение не имеет решений вообще - то поиск решения будет очень затруднён.
• метод работает только для целых чисел или для простых дробей, любое округление приводит к тому что решение не удаётся найти
• В 1969 году Штрассен доказал, что большие матрицы можно оптимизировать перемножение более оптимально чем в методе Гаусса. Таким образом, для больших СЛАУ метод Гаусса не оптимален по скорости. Думаю 7-я степень для современных ПК - прпоблем не будет.