Description

Solve the linear system Ax = y, where:

• A is an n×n upper-triangular matrix,

• x and y are n-dimensional vectors.

To save memory, only the upper triangle of A (including the diagonal) is stored in a one-dimensional array in row-major packed order.

For 0 ≤ i ≤ j < n, the element Ai, j is stored consecutively for rows i = 0,1,…,n−1
The linear index of ​ in the packed array is:

 

Implement back-substitution 高斯消去法 in the function below:

void upper_solver(double *A, double *x, double *y, int n); 

• A points to the packed upper-triangular data of size n*(n+1)/2.

• y is the right-hand-side vector.

• x is the output vector; store the solution in x.

• You may assume all diagonal entries of A are non-zero.

Example Main Function

#include <stdio.h>
#define N 256

void upper_solver(double *A, double *x, double *y, int n);

int main(void)
{
    int i, j;
    int n;
    double A[N * (N + 1) / 2];
    double *aptr = A;
    double x[N];
    double y[N];
   
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        for (j = i; j < n; j++) {
            scanf("%lf", aptr);
            aptr++;
        }
       
    for (i = 0; i < n; i++)
        scanf("%lf", &y[i]);
   
    upper_solver(A, x, y, n);
   
    for (i = 0; i < n; i++)
        printf("%f\n", x[i]);
   
    return 0;
}

Hint  back-substitution 高斯消去法

Suppose we want to solve Ax=y where A is a 3×3 upper-triangular matrix:

Step 1: Solve for the last variable x₂

From the last row:

4x₂​=8 ⇒ x₂​=2

---

Step 2: Solve for x₁​ using the second row

3x_1​+2x₂​=4

Substitute x₂=2

3x₁​+4=4 ⇒ x_1​=0

---

Step 3: Solve for x₀ using the first row

2x₀​+1⋅x₁​−1⋅x_2​=1

Substitute x₁​=0,x₂​=2:

2x₀​−2=1 ⇒ x₀​=1.5

Final Solution

 

Input

• The first line contains an integer n (0 < n ≤ 256), representing the size of the matrix.

• The next n*(n+1)/2 floating-point numbers describe the upper triangle of the n×n matrix A, stored in row-major packed order:

  • For each rowi = 0,1,…,n−1, input the elements A_i,i ,A_{i,i+1, ... ,} A_i,n-1

• The final line contains n floating-point numbers, representing the elements of the vector y.

Example

// Sample input 1

3
1.0 2.0 3.0
2.0 1.0
4.0
2.0 3.0 -4.0

Here, 

• n=3

• Upper triangle of Matrix A (packed form)：

  

• Vector y is

^​

 

Output

• Output n floating-point numbers, each on a separate line, representing the solution vector x of the system Ax=y

• Use default %f formatting (six digits after the decimal point in C).

Sample Input  Download

Sample Output  Download

Tags

Discuss