Linear Systems: Direct and Iterative Methods in College Algebra

스터디 가이드 - 스마트 노트

자료에 맞춘 맞춤형 노트, 핵심 정의, 예시, 맥락을 확장해 제공합니다.

Linear Systems

Overview of Methods for Solving Linear Systems

Solving linear systems is a fundamental topic in College Algebra, especially in the context of systems and matrices. This section introduces direct and iterative methods, including Gaussian elimination, partial pivoting, LU and PLU factorization, conditioning, and iterative solvers such as Jacobi, Gauss–Seidel, and SOR.

Direct Methods: Transform the system to a simpler form and solve exactly.
Iterative Methods: Start from an initial guess and improve the solution step by step.
Factorization: Decompose matrices to facilitate repeated solutions.
Conditioning: Analyze sensitivity to input changes.

Gaussian Elimination

Goal and Process

Gaussian elimination transforms the coefficient matrix of a linear system into an upper-triangular form using row operations, followed by back substitution to solve for the variables.

Allowed Row Operations: Swap rows, multiply a row by a nonzero number, add a multiple of one row to another.
Preservation of Solutions: Each operation produces an equivalent system with the same solution set.
Elimination Multiplier: For a pivot in column k, the multiplier is .
Upper-Triangular Matrix: Zeros are created below the diagonal, simplifying the system.

Example: Eliminating x below the first pivot in a 3x3 system.

Augmented matrix for Gaussian elimination Row operations in Gaussian elimination Elimination of x below the first pivot Result after elimination Updated matrix after elimination

Back Substitution

Once the matrix is upper-triangular, solve for the variables starting from the last equation and moving upward.

Verification: Substitute the solution back into the original equations to check correctness.

Back substitution step Verification of solution

Partial Pivoting

Necessity and Algorithm

Partial pivoting is required when a zero or very small pivot is encountered, which can cause division by zero or numerical instability. The algorithm swaps rows to place the largest-magnitude entry in the current column as the pivot.

Algorithm Steps:
1. Choose the pivot row with the largest absolute value in the current column.
2. Swap rows if necessary.
3. Eliminate entries below the pivot.
Numerical Stability: Choosing a large pivot reduces rounding errors.

System requiring partial pivoting Division by zero without pivoting Row swap for partial pivoting Permuted augmented matrix Elimination after pivoting Back substitution after pivoting Verification after pivoting

LU and PLU Factorization

LU Factorization

LU factorization decomposes a matrix A into a product of a lower triangular matrix L and an upper triangular matrix U. This allows efficient solution of multiple systems with the same coefficient matrix.

L: Stores elimination multipliers below the diagonal.
U: Stores the upper-triangular result of elimination.
Factorization: (without row swaps), (with row swaps).

Example: Constructing L and U from elimination steps.

Matrix	Form
L	Lower triangular with ones on the diagonal and multipliers below
U	Upper triangular after elimination

PLU Factorization and Permutation Matrix

When row swaps are needed, a permutation matrix P records the swaps. The factorization becomes or depending on convention.

P: Permutation matrix, records row swaps.
L: Elimination multipliers after pivoting.
U: Upper-triangular matrix after elimination.

Example: Applying P to reorder rows before elimination.

Step	Description
Pivot	Swap rows to place largest pivot
Eliminate	Store multipliers in L
Result	PA = LU

Accuracy and Conditioning

Forward Error and Residual

Forward error measures the difference between the exact and approximate solution, while the residual measures how well the approximation satisfies the original equations.

Forward Error:
Residual:
Norms: , , for vectors; for matrices.

Example: A small residual does not always imply a small forward error, especially in ill-conditioned systems.

Condition Number

The condition number quantifies the sensitivity of the solution to changes in the input. A large condition number indicates an ill-conditioned system.

Definition:
Interpretation: Near 1 is well-conditioned; large values mean sensitive.

Iterative Methods

Jacobi, Gauss–Seidel, and SOR Methods

Iterative methods improve an approximation to the solution by repeated sweeps through the equations. They are especially useful for large systems.

Jacobi: Uses only previous iteration values.
Gauss–Seidel: Uses new values as soon as they are computed.
SOR (Successive Over-Relaxation): Introduces a relaxation parameter to accelerate convergence.

Matrix Splitting: where D is diagonal, L is strictly lower, U is strictly upper.

Method	Update Formula	Values Used
Jacobi	Divide by diagonal entries	Old values only
Gauss–Seidel	Forward substitution	New values immediately
SOR	Relaxation:	Controlled by

Convergence Criteria

Convergence is guaranteed for strictly diagonally dominant systems. Practical stopping criteria include relative residual, maximum iteration count, and step-size checks.

Preferred Test:
Safeguards: Maximum iterations, step-size monitoring, report convergence status.

Summary of Workflow

Solving linear systems involves a connected workflow:

Use Gaussian elimination to create zeros below the diagonal.
Apply partial pivoting for stability.
Factor matrices as LU or PLU for efficient repeated solutions.
Check conditioning using norms and the condition number.
Always compute the residual after solving.
Use iterative methods for large or sparse systems.

A trustworthy numerical answer requires a suitable algorithm, a residual check, and an understanding of the problem conditioning.