- Background In This Programming Assignment You Will Be Responsible For Implementing A Solver For The System Of Linear 1 (64.78 KiB) Viewed 21 times
= Background: In this programming assignment, you will be responsible for implementing a solver for the system of linear equations Az = 5 where • A is an n x n matrix whose columns are linearly independent .KER" . DER" To implement the solver, you must apply the following theorem: THM QR-Factorization If A E Fmxn matrix with linearly independent columns at,a..... then there exists, 1. an m x n matrix Q whose columns ū1, u,..., ū are orthonormal, and 2. an n x n matrix R that is upper triangular and whose entries are defined by, Pij (una) for i si for i>j such that A = QR. This referred to as the QR factorization (or decomposition) of matrix A. To find matrices Q and R from the QR Factorization Theorem, we apply Gram-Schimdt process to the columns of A. Then, the columns of Q will be the orthonormal vectors u, üs..., ū, returned by the Gram Schimdt process, and the entries rij of R will be computed using each column ū as defined in the theorem. Luckily, you do not need to implement this process. A Python library called numpy contains a module called linals with a function called gr() that returns the matrices Q and R in the QR factorization of a matrix A. Try running the following cell to see how it works. {na U2, ,
In (): import numpy as np A = [[1, 1, 0], [0, 1, 1], [1, 0, 1]] Q, R = np.linalg.qr(A) print("o =\n", o) print("\nR =\n", R) print("\n\nOriginal A =\n", Matrix(A)) print("\nQ * R =\n", Matrix(0) * Matrix(R)) Your Task: а Assuming A E Rixn is a Matrix object, and b ER" is a vec object, implement a function solve_gr(A, b) that uses the QR-factorization of A to compute and return the solution to the system A = D. Hints: = 1. If A = QR, then Az = 5 becomes QR* b. What happens if we multiply both sides of the equation by the transpose of Q? i.e., What does O'QRT = Q7 simplify to? 2. Part of your code for the solvers in CA #6 will come in handy. In ( ): cdef solve_qr(A, b): #todo pass In (): "" "TESTER CELL"** A = Matrix([[2, -2, 18], [2, 1, 0], [1, 2, 0]]) x_true = Vec([3, 4, 5]) b = A* X true print("Expected:", x_true) x = solve_qr(A, b) print("Returned:", x)