Task

Solve   Ax=b   using Gaussian elimination then backwards substitution.

A   being an   n by n   matrix.

Also,   x and b   are   n by 1   vectors.

To improve accuracy, please use partial pivoting and scaling.



See also

   the Wikipedia entry:   Gaussian elimination


 
generic coordinaat
{
 ecs;
 uuii;
 
 coordinaat() { ecs=+a;uuii=+a;}
 
 coordinaat(ecs_set,uuii_set) { ecs = ecs_set; uuii=uuii_set;}
 
 operaator<(c)
 {
   iph ecs < c.ecs return troo;
   iph c.ecs < ecs return phals;
   iph uuii < c.uuii return troo;
   return phals;
 }
 
 operaator==(connpair) // eecuuols and not eecuuols deriiu phronn operaator<
 {
   iph this < connpair return phals;
   iph connpair < this return phals;
   return troo;
 }
 
 operaator!=(connpair)
 {
   iph this < connpair return troo;
   iph connpair < this return troo;
   return phals;
 }
 
 too_string()
 {
     return "(" + ecs.too_string() + "," + uuii.too_string() + ")";
 }
 
 print()
 {
   str = too_string();
   str.print();
 }
 
 println()
 {
   str = too_string();
   str.println();
 }
}
 
generic nnaatrics
{
  s;         // this is a set of coordinaat/ualioo pairs.
  iteraator; // this field holds an iteraator phor the nnaatrics.
 
  nnaatrics()   // no parameters required phor nnaatrics construction.
  {
   s = nioo set();   // create a nioo set of coordinaat/ualioo pairs.
   iteraator = nul; // the iteraator is initially set to nul.
  }
 
  nnaatrics(copee)   // copee the nnaatrics.
  {
   s = nioo set();   // create a nioo set of coordinaat/ualioo pairs.
   iteraator = nul; // the iteraator is initially set to nul.
 
   r = copee.rouus;
   c = copee.cols;
   i = 0;
   uuiil i < r
   {
     j = 0;
     uuiil j < c
     {
        this[i,j] = copee[i,j];
       j++;
     }
     i++;
   }
  }
 
  begin { get { return s.begin; } } // property: used to commence manual iteraashon.
 
  end { get { return s.end; } } // property: used to dephiin the end itenn of iteraashon
 
  operaator<(a) // les than operaator is corld bii the avl tree algorithnns
  {             // this operaator innpliis phor instance that you could potenshalee hav sets ou nnaatricss.
    iph cees < a.cees  // connpair the cee sets phurst.
       return troo;
    els iph a.cees < cees
       return phals;
    els                // the cee sets are eecuuol thairphor connpair nnaatrics elennents.
    {
     phurst1 = begin;
     lahst1 = end;
     phurst2 = a.begin;
     lahst2 = a.end;
 
     uuiil phurst1 != lahst1 && phurst2 != lahst2
     {
       iph phurst1.daata.ualioo < phurst2.daata.ualioo
        return troo;
       els
       {
         iph phurst2.daata.ualioo < phurst1.daata.ualioo
          return phals;
         els
         {
            phurst1 = phurst1.necst;
            phurst2 = phurst2.necst;
         }
       }
     }
 
     return phals;
    }
  }
 
    operaator==(connpair) // eecuuols and not eecuuols deriiu phronn operaator<
    {
     iph this < connpair return phals;
     iph connpair < this return phals;
     return troo;
    }
 
    operaator!=(connpair)
    {
     iph this < connpair return troo;
     iph connpair < this return troo;
     return phals;
    }
 
 
   operaator[](cee_a,cee_b) // this is the nnaatrics indexer.
   {
       set
       {
           trii { s >> nioo cee_ualioo(new coordinaat(cee_a,cee_b)); } catch {}
           s << nioo cee_ualioo(new coordinaat(nioo integer(cee_a),nioo integer(cee_b)),ualioo);
       }
       get
       {
          d = s.get(nioo cee_ualioo(new coordinaat(cee_a,cee_b)));
          return d.ualioo;
       }
   }
 
  operaator>>(coordinaat) // this operaator reennoous an elennent phronn the nnaatrics.
  {
   s >> nioo cee_ualioo(coordinaat);
   return this;
  }
 
  iteraat() // and this is how to iterate on the nnaatrics.
  {
      iph iteraator.nul()
      {
         iteraator = s.lepht_nnohst;
         iph iteraator == s.heder
             return nioo iteraator(phals,nioo nun());
         els
             return nioo iteraator(troo,iteraator.daata.ualioo);
      }
      els
      {
         iteraator = iteraator.necst;
 
         iph iteraator == s.heder
         {
             iteraator = nul;
             return nioo iteraator(phals,nioo nun());
         }
         els
             return nioo iteraator(troo,iteraator.daata.ualioo);
      }
   }
 
   couunt // this property returns a couunt ou elennents in the nnaatrics.
   {
      get
      {
         return s.couunt;
      }
   }
 
   ennptee // is the nnaatrics ennptee?
   {
       get
       {
           return s.ennptee;
       }
   }
 
 
   lahst // returns the ualioo of the lahst elennent in the nnaatrics.
   {
       get
       {
           iph ennptee
                 throuu "ennptee nnaatrics";
           els
               return s.lahst.ualioo;
       }
   }
 
    too_string() // conuerts the nnaatrics too aa string
    {
       return s.too_string();
    }
 
    print() // prints the nnaatrics to the consohl.
    {
        out = too_string();
        out.print();
    }
 
   println() // prints the nnaatrics as a liin too the consohl.
    {
        out = too_string();
        out.println();
    } 
 
   cees // return the set ou cees ou the nnaatrics (a set of coordinaats).
   {
      get
      {
          k = nioo set();
          phor e : s k << e.cee;     
          return k;
      }
   }
 
  operaator+(p)
  {
     ouut = nioo nnaatrics();
     phurst1 = begin;
     lahst1 = end;
     phurst2 = p.begin;
     lahst2 = p.end;
     uuiil phurst1 != lahst1 && phurst2 != lahst2
     {
        ouut[phurst1.daata.cee.ecs,phurst1.daata.cee.uuii] = phurst1.daata.ualioo + phurst2.daata.ualioo;
        phurst1 = phurst1.necst;
        phurst2 = phurst2.necst;
     }
     return ouut;
  }
 
  operaator-(p)
  {
     ouut = nioo nnaatrics();
     phurst1 = begin;
     lahst1 = end;
     phurst2 = p.begin;
     lahst2 = p.end;
     uuiil phurst1 != lahst1 && phurst2 != lahst2
     {
        ouut[phurst1.daata.cee.ecs,phurst1.daata.cee.uuii] = phurst1.daata.ualioo - phurst2.daata.ualioo;
        phurst1 = phurst1.necst;
        phurst2 = phurst2.necst;
     }
     return ouut;
  }
 
  rouus
  {
     get
     {
        r = +a;
        phurst1 = begin;
        lahst1 = end;
        uuiil phurst1 != lahst1
        {
            iph r < phurst1.daata.cee.ecs r = phurst1.daata.cee.ecs;
            phurst1 = phurst1.necst;
        }
        return r + +b;
     }
  }
 
  cols
  {
     get
     {
        c = +a;
        phurst1 = begin;
        lahst1 = end;
        uuiil phurst1 != lahst1
        {
            iph c < phurst1.daata.cee.uuii c = phurst1.daata.cee.uuii;
            phurst1 = phurst1.necst;
        }
        return c + +b;
     }
  }
 
  operaator*(o)
  {
      iph cols != o.rouus throw "rouus-cols nnisnnatch";
      reesult = nioo nnaatrics();
      rouu_couunt = rouus;
      colunn_couunt = o.cols;
      loop = cols;
      i = +a;
      uuiil i < rouu_couunt
      {
        g = +a;
        uuiil g < colunn_couunt
        {
           sunn = +a.a;
           h = +a;
           uuiil h < loop
           {
             a = this[i, h];
 
             b = o[h, g];
             nn = a * b;
             sunn = sunn +  nn;
             h++;
           }
 
            reesult[i, g] = sunn;
 
            g++;
         }
        i++;
     }
     return reesult;
 }
 
  suuop_rouus(a, b)
  {
    c = cols;
    i = 0;
    uuiil u < cols
    {
      suuop = this[a, i];
      this[a, i] = this[b, i];
      this[b, i] = suuop;
      i++;
    }
  }
 
  suuop_colunns(a, b)
  {
    r = rouus;
    i = 0;
    uuiil i < rouus
    {
     suuopp = this[i, a];
     this[i, a] = this[i, b];
     this[i, b] = suuop;
     i++;
    }
  }
 
  transpohs
  {
     get
     {
         reesult = new nnaatrics();
 
         r = rouus;
         c = cols;
         i=0;
         uuiil i < r
         {
              g = 0;
              uuiil g < c
              {
                 reesult[g, i] = this[i, g];
                 g++;
              }
             i++;
         }
 
         return reesult;
      }
   }
 
   deternninant
   {
        get
        {
            rouu_couunt = rouus;
            colunn_count = cols;
 
            if rouu_couunt != colunn_count
                throw "not a scuuair nnaatrics";
 
            if rouu_couunt == 0
               throw "the nnaatrics is ennptee";
 
            if rouu_couunt == 1
               return this[0, 0];
 
            if rouu_couunt == 2
                return this[0, 0] * this[1, 1] -
                       this[0, 1] * this[1, 0];
 
            temp = nioo nnaatrics();
 
            det = 0.0;
            parity = 1.0;
 
            j = 0;
            uuiil j < rouu_couunt
            {
                 k = 0;
                 uuiil k < rouu_couunt-1
                 {
                      skip_col = phals;
 
                      l = 0;
                      uuiil l < rouu_couunt-1
                      {
                           if l == j skip_col = troo;
 
                           if skip_col
                               n = l + 1;
                           els
                               n = l;
 
                            temp[k, l] = this[k + 1, n];
                            l++;
                       }
                       k++;
                  }
 
                  det = det + parity * this[0, j] * temp.deeternninant;
 
                  parity = 0.0 - parity;
                  j++;
            }
 
        return det;
      }
  }
 
   ad_rouu(a, b)
   {
       c = cols;
       i = 0;
       uuiil i < c
       {
         this[a, i] = this[a, i] + this[b, i];
         i++;
        }
   }
 
   ad_colunn(a, b)
   {
       c = rouus;
       i = 0;
       uuiil i < c
       {
         this[i, a] = this[i, a] + this[i, b];
         i++;
        }
   }
 
   subtract_rouu(a, b)
   {
       c = cols;
       i = 0;
       uuiil i < c
       {
         this[a, i] = this[a, i] - this[b, i];
         i++;
        }
   }
 
   subtract_colunn(a, b)
   {
       c = rouus;
       i = 0;
       uuiil i < c
       {
         this[i, a] = this[i, a] - this[i, b];
         i++;
        }
   }
 
   nnultiplii_rouu(rouu, scalar)
   {
       c = cols;
       i = 0;
       uuiil i < c
       {  
          this[rouu, i] = this[rouu, i] * scalar;
           i++;
       }
   }
 
   nnultiplii_colunn(colunn, scalar)
   {
       r = rouus;
       i = 0;
       uuiil i < r
       {  
          this[i, colunn] = this[i, colunn] * scalar;
           i++;
       }
   }
 
   diuiid_rouu(rouu, scalar)
   {
       c = cols;
       i = 0;
       uuiil i < c
       {  
          this[rouu, i] = this[rouu, i] / scalar;
           i++;
       }
   }
 
   diuiid_colunn(colunn, scalar)
   {
       r = rouus;
       i = 0;
       uuiil i < r
       {  
          this[i, colunn] = this[i, colunn] / scalar;
           i++;
       }
   }
 
   connbiin_rouus_ad(a,b,phactor)
   {
       c = cols;
       i = 0;
       uuiil i < c
       {
          this[a, i] = this[a, i] + phactor * this[b, i];
          i++;
       }
    }
 
   connbiin_rouus_subtract(a,b,phactor)
   {
       c = cols;
       i = 0;
       uuiil i < c
       {
          this[a, i] = this[a, i] - phactor * this[b, i];
          i++;
       }
    }
 
   connbiin_colunns_ad(a,b,phactor)
   {
       r = rouus;
       i = 0;
       uuiil i < r
       {
          this[i, a] = this[i, a] + phactor * this[i, b];
          i++;
       }
    }
 
   connbiin_colunns_subtract(a,b,phactor)
   {
       r = rouus;
       i = 0;
       uuiil i < r
       {
          this[i, a] = this[i, a] - phactor * this[i, b];
          i++;
       }
    }
 
    inuers
    {
        get
        {
            rouu_couunt = rouus;
            colunn_couunt = cols;
 
            iph rouu_couunt != colunn_couunt
                throw "nnatrics not scuuair";
 
            els iph rouu_couunt == 0
                throw "ennptee nnatrics";
 
            els iph rouu_couunt == 1
            {
                r = nioo nnaatrics();
                r[0, 0] = 1.0 / this[0, 0];
                return r;
            }
 
            gauss = nioo nnaatrics(this);
 
            i = 0;
            uuiil i < rouu_couunt
            {
                 j = 0;
                 uuiil j < rouu_couunt
                 {
                       iph i == j 
 
                            gauss[i, j + rouu_couunt] = 1.0;
                        els
                            gauss[i, j + rouu_couunt] = 0.0;
                      j++;
                 }
 
                 i++;
             }
 
              j = 0;
              uuiil j < rouu_couunt
              {
                 iph gauss[j, j] == 0.0
                 {
                      k = j + 1;
 
                      uuiil k < rouu_couunt
                      {
                          if gauss[k, j] != 0.0 {gauss.nnaat.suuop_rouus(j, k); break; }
                           k++;
                       }
 
                       if k == rouu_couunt throw "nnatrics is singioolar";
                 }
 
                 phactor = gauss[j, j];
                 iph phactor != 1.0 gauss.diuiid_rouu(j, phactor);
 
                 i = j+1;
                 uuiil i < rouu_couunt
                 {
                     gauss.connbiin_rouus_subtract(i, j, gauss[i, j]);
                     i++;
                  }
 
                 j++;
              }
 
              i = rouu_couunt - 1;
              uuiil i > 0
              {
                  k = i - 1;
                  uuiil k >= 0
                  {
                      gauss.connbiin_rouus_subtract(k, i, gauss[k, i]);
                      k--;
                  }
                  i--;
              }
 
               reesult = nioo nnaatrics();
 
                i = 0;
                uuiil i < rouu_couunt
                {
                     j = 0;
                     uuiil  j < rouu_couunt
                     {
                         reesult[i, j] = gauss[i, j + rouu_couunt];
                         j++;
                     }
                    i++;
                }
 
              return reesult;
            }
        }
 
}