Массивы

[<атрибуты>] [<модификаторы>] <тип> <объявители>;

<тип>[] <объявители>;

int[] a, b, c;

double[] x= {5.5, 6.6, 7.7};

int[] d= new int[5];

public void TestDeclaration()
  {
  	//объявляются три одномерных массива A,B,C
  	int[] A = new int[5], B= new int[5], C= new int[5];
  	Arrs.CreateOneDimAr(A);
  	Arrs.CreateOneDimAr(B);
  	for(int i = 0; i<5; i++)
    C[i] = A[i] + B[i];
  	//объявление массива с явной инициализацией
  	int[] x ={5,5,6,6,7,7};
  	//объявление массивов с отложенной инициализацией
  	int[] u,v;
  	u = new int[3];
  	for(int i=0; i<3; i++) u[i] =i+1;
  	// v = {1,2,3}; //присваивание константного массива недопустимо
  	v = new int[4];  	
  	v = u; //допустимое присваивание
  	Arrs.PrintAr1("A", A); Arrs.PrintAr1("B", B);
  	Arrs.PrintAr1("C", C); Arrs.PrintAr1("X", x);
  	Arrs.PrintAr1("U", u); Arrs.PrintAr1("V", v);
  }

public static void CreateOneDimAr(int[] A)
  {    	
  	for(int i = 0; i<A.GetLength(0);i++)
    A[i] = rnd.Next(1,100);
  }//CreateOneDimAr

private  static Random rnd = new Random();

public static void PrintAr1(string name,int[] A)
  {
  	Console.WriteLine(name);
  	for(int i = 0; i<A.GetLength(0);i++)
    Console.Write("\t" + name + "[{0}]={1}", i, A[i]);
  	Console.WriteLine();  	
  }//PrintAr1

public void TestDynAr()
  {
  	//объявление динамического массива A1
  	Console.WriteLine("Введите число элементов массива A1");
  	int size = int.Parse(Console.ReadLine());
  	int[] A1 = new int[size];
  	Arrs.CreateOneDimAr(A1);
  	Arrs.PrintAr1("A1",A1);
  }//TestDynAr

<тип>[, … ,] <объявители>;

public void TestMultiArr()
  {
  	int[,]matrix = {
          {1,2},
          {3,4}
     };
  	Arrs.PrintAr2("matrix", matrix);
  }//TestMultiArr

public void TestMultiMatr()
  {
  	int n1, m1, n2, m2,n3, m3;
  	Arrs.GetSizes("MatrA",out n1,out m1);
  	Arrs.GetSizes("MatrB",out n2,out m2);
  	Arrs.GetSizes("MatrC",out n3,out m3);
  	int[,]MatrA = new int[n1,m1], MatrB = new int[n2,m2];
  	int[,]MatrC = new int[n3,m3];
  	Arrs.CreateTwoDimAr(MatrA); Arrs.CreateTwoDimAr(MatrB);
  	Arrs.MultMatr(MatrA, MatrB, MatrC);
  	Arrs.PrintAr2("MatrA",MatrA); Arrs.PrintAr2("MatrB",MatrB);
  	Arrs.PrintAr2("MatrC",MatrC);  	
  }//TestMultiMatr

public void MultMatr(int[,]A, int[,]B, int[,]C)
  {
  	if (A.GetLength(1) != B.GetLength(0))
    Console.WriteLine("MultMatr: ошибка размерности!");
  	else
    for(int i = 0; i < A.GetLength(0); i++)
    	for(int j = 0; j < B.GetLength(1); j++)
    	{
      int s=0;
      for(int k = 0; k < A.GetLength(1); k++)
  s+= A[i,k]*B[k,j];
      C[i,j] = s;
    	}
  }//MultMatr

//массив массивов - формальный пример
   	//объявление и инициализация
  	int[][] jagger = new int[3][]
  {
        new int[] {5,7,9,11},
        new int[] {2,8},
        new int[] {6,12,4}
  };

int[][] jagger1 = new int[3][]
  {
  new int[4],
  new int[2],
  new int[3]
  };

int[][] jagger2 =
   {
  new int[4],
  new int[2],
  new int[3]
  };

/// <summary>
/// массив массивов -"Отцы и дети"
/// </summary>
public void GenTree()
 {            
    int Fcount = 3;
    string[] Fathers = new string[Fcount];
    Fathers[0] = "Николай"; Fathers[1] = "Сергей"; Fathers[2] = "Петр";
    string[][] Children = new string[Fcount][];
    Children[0] = new string[] {"Ольга", "Федор"};
    Children[1] = new string[] {"Сергей", "Валентина", "Ира", "Дмитрий"};
    Children[2] = new string[] {"Мария", "Ирина", "Надежда"};
    Arrs.PrintAr3(Fathers, Children);
  }

/// <summary>
        /// Печать дерева "Отцы и дети",
        /// заданного массивами Fathers и Children
        /// </summary>
        /// <param name="Fathers">массив отцов</param>
        /// <param name="Children"> массив массивов детей</param>
        public static void PrintAr3(string[] Fathers, string[][] Children)
        {
            for (int i = 0; i < Fathers.Length; i++)
            {
                Console.WriteLine("Отец : {0}; Его дети:", Fathers[i]);
                for (int j = 0; j < Children[i].Length; j++)
                    Console.Write(Children[i][j] + " ");
                Console.WriteLine();
            }
        }//PrintAr3

//fields
  int n = 0;
  double[] mas;
  int currentindex = 0;  
  double ditem = 0;
  const string SIZE = "Корректно задайте размер массива!";
  const string INVITE = "Введите число в формате m[,n]";
  const string EMPTY =  "Массив пуст!";
  const string ITEMB =  "mas[";
  const string ITEME =  "] = ";
  const string FULL =   "Ввод недоступен!";
  const string OK =     "Корректный ввод!";
  const string ERR =    "Ошибка ввода числа! Повторите ввод!";

private void buttonCreateArray_Click(object sender, EventArgs e)
  {
      try
      {
    n = Convert.ToInt32(textBoxN.Text);
    mas = new double[n]; 
    labelInvite.Text = INVITE;
    labelItem.Text = ITEMB + "0" + ITEME;
    labelResult.Text = EMPTY;
    textBoxItem.ReadOnly = false;
    listBox1.Items.Clear();
    comboBox1.Items.Clear();
    checkedListBox1.Items.Clear();
    comboBox1.Items.Clear();
    currentindex = 0;
      }
      catch (Exception)
      {
    labelResult.Text = SIZE;
      }
  }

private void buttonAddItem_Click(object sender, EventArgs e)
  {
      //Заполнение массива элементами
      if (GetItem())
      {
    mas[currentindex] = ditem;
    listBox1.Items.Add(mas[currentindex]);
    checkedListBox1.Items.Add(mas[currentindex]);
    comboBox1.Items.Add(mas[currentindex]);
    currentindex++;
    labelItem.Text = ITEMB + currentindex + ITEME;
    textBoxItem.Text = "";
    labelResult.Text = OK;
    if (currentindex == n)
    {
        labelInvite.Text = "";
        labelItem.Text = "";
        labelResult.Text = FULL;
        textBoxItem.Text = "";
        textBoxItem.ReadOnly = true;
    }
   }
}

/// <summary>
   /// Ввод с контролем текущего элемента массива
   /// </summary>
   /// <returns>true в случае корректного ввода значения</returns>
   bool GetItem()
   {
       string item = textBoxItem.Text;
       bool res = false;
       if (item == "")
      labelResult.Text = INVITE;
       else
       {
      try
      {
          ditem = Convert.ToDouble(item);
          res = true;
      }
      catch(Exception)
      {
          labelResult.Text = ERR;
      }
       }
       return res;
   }

Организация ввода-вывода двумерных массивов

Ввод двумерного массива немногим отличается от ввода одномерного массива. Сложнее обстоит дело с выводом двумерного массива, если при выводе пытаться отобразить структуру массива. К сожалению, все три элемента управления, хорошо справляющиеся с отображением одномерного массива, плохо приспособлены для показа структуры двумерного массива. Хотя у того же элемента показан пример формы, поддерживающей работу по вводу и выводу двумерного массива.

(рис 6.5) Форма, поддерживающая ввод и вывод двумерного массива

Интерфейс формы схож с тем, что использовался для организации работы с одномерным массивом. Схожа и программная организация ввода-вывода элементов массива. Поэтому я не буду приводить код, поддерживающий работу с формой TwoDimArrayForm, надеясь, что читатель при желании сможет его восстановить. Остановлюсь лишь на одном моменте, позволяющем отображать двумерный массив в элементе управления ListBox так, чтобы сохранялась структура строк и столбцов массива. Этого можно добиться за счет программной настройки размеров элемента управления ListBox:

listBox1.Height = n * HEIGHT_LINE;
                listBox1.Width = m * 2 * HEIGHT_LINE;

Константа HEIGHT_LINE задает высоту строки в списке. Вначале водятся элементы первого столбца; когда весь столбец введен, автоматически следующее вводимое значение будет отображаться в первой строке в следующем столбце.

В общей ситуации, когда значения, вводимые пользователем, могут колебаться в широком диапазоне, трудно гарантировать отображение структуры двумерного массива. Однако ситуация не безнадежна. Есть и другие, более мощные и более подходящие для наших целей элементы управления. Если на элементах ListBox и подобных ему я останавливаться не буду, оставляя их для самостоятельного изучения, то об элементе DataGridView расскажу подробнее.

Элемент управления DataGridView и отображение массивов

Элемент управления DataGridView является последней новинкой в серии табличных элементов DataGrid, позволяющих отображать таблицы. Главное назначение этих элементов - связывание с таблицами внешних источников данных, прежде всего с таблицами баз данных. Мы же сейчас рассмотрим другое его применение - в интерфейсе, позволяющем пользователю вводить и отображать матрицы - двумерные массивы.

Рассмотрим классическую задачу умножения прямоугольных матриц показан возможный вид формы, поддерживающей работу пользователя. Форма показана в тот момент, когда пользователь уже задал размеры и значения исходных матриц, выполнил умножение матриц и получил результат.

(рис 6.6) Форма с элементами DataGridView, поддерживающая работу с матрицами

На форме расположены три текстовых окна для задания размеров матриц, три элемента . В них отображается информация, связанная с формой и отдельными элементами управления. Текст у невидимых на рисунке меток появляется тогда, когда обнаруживается, что пользователь некорректно задал значение какого-либо элемента исходных матриц.

А теперь перейдем к описанию того, как этот интерфейс реализован. В классе Form2, которому принадлежит наша форма, зададим поля, определяющие размеры матриц, и сами матрицы:

//поля класса Form
        int m, n, p;    //размеры матриц
        double[,] A, B, C;  //сами матрицы

Рассмотрим теперь, как выглядит обработчик события "Click" командной кнопки "Создать DataGridView". Предполагается, что пользователь разумен и, прежде чем нажать эту кнопку, задает размеры матриц в соответствующих текстовых окнах. Напомню, что при перемножении матриц размеры матриц должны быть согласованы - число столбцов первого сомножителя должно совпадать с числом строк второго сомножителя, а размеры результирующей матрицы определяются размерами сомножителей. Поэтому для трех матриц в данном случае достаточно задать не шесть, а три параметра, определяющие размеры.

Обработчик события выполняет три задачи - создает сами матрицы, осуществляет чистку элементов управления DataGridView, удаляя предыдущее состояние, затем добавляет столбцы и строки в эти элементы в полном соответствии с заданными размерами матриц. Вот текст обработчика:

private void button1_Click(object sender, EventArgs e)
   {
       //создание матриц
       m = Convert.ToInt32(textBox1.Text);
       n = Convert.ToInt32(textBox2.Text);
       p = Convert.ToInt32(textBox3.Text);
       A = new double[m, n];
       B = new double[n, p];
       C = new double[m, p];
      //Чистка DGView, если они не пусты
       int k =0;
       k = dataGridView1.ColumnCount;
       if (k != 0)
           for (int i = 0; i < k; i++)
               dataGridView1.Columns.RemoveAt(0);           
       dataGridView2.Columns.Clear();
       dataGridView3.Columns.Clear();      
       //Заполнение DGView столбцами 
       AddColumns(n, dataGridView1);
       AddColumns(p, dataGridView2);
       AddColumns(p, dataGridView3);
       //Заполнение DGView строками
       AddRows(m, dataGridView1);
       AddRows(n, dataGridView2);
       AddRows(m, dataGridView3);
   }

Прокомментирую этот текст.

Прием размеров и создание матриц, надеюсь, не требует дополнительных комментариев.

Чистка предыдущего состояния элементов DataGridView сводится к удалению столбцов. Продемонстрированы два возможных способа выполнения этой операции. Для первого элемента показано, как можно работать с коллекцией столбцов. Организуется цикл по числу столбцов коллекции, и в цикле выполняется метод RemoveAt, аргументом которого является индекс удаляемого столбца. Поскольку после удаления столбца происходит перенумерация столбцов, на каждом шаге цикла удаляется первый столбец, индекс которого всегда равен нулю. Удаление столбцов коллекции можно выполнить одним махом - вызывая метод Clear() коллекции, что и делается для остальных двух элементов DataGridView.

После чистки предыдущего состояния, можно задать новую конфигурацию элемента, добавив в него вначале нужное количество столбцов, а затем и строк. Эти задачи выполняют специально написанные процедуры AddColumns и AddRows. Вот их текст:

private void AddColumns(int n, DataGridView dgw)
   {
       //добавляет n столбцов в элемент управления dgw
       //Заполнение DGView столбцами
       DataGridViewColumn column;
       for (int i = 0; i < n; i++)
       {
           column = new DataGridViewTextBoxColumn();
           column.DataPropertyName = "Column" + i.ToString();
           column.Name = "Column" + i.ToString();
           dgw.Columns.Add(column);
       }      
   }
   private void AddRows(int m, DataGridView dgw)
   {
       //добавляет m строк в элемент управления dgw       
       //Заполнение DGView строками
       for (int i = 0; i < m; i++)
       {
        dgw.Rows.Add();
           dgw.Rows[i].HeaderCell.Value
               = "row" + i.ToString();
       }
   }

Приведу краткий комментарий.

Создаются столбцы в коллекции Columns по одному. В цикле по числу столбцов матрицы, которую должен отображать элемент управления DataGridView, вызывается метод Add этой коллекции, создающий очередной столбец. Одновременно в этом же цикле создается и имя столбца (свойство Name ), отображаемое в форме. Показана возможность формирования еще одного имени ( DataPropertyName ), используемого при связывании со столбцом таблицы внешнего источника данных. В нашем примере это имя не используется.

Создав столбцы, нужно создать еще и нужное количество строк у каждого из элементов DataGridView. Делается это аналогичным образом, вызывая метод Add коллекции Rows. Чуть по-другому задаются имена строк - для этого используется специальный объект HeaderCell, имеющийся у каждой строки и задающий ячейку заголовка.

После того как сформированы строки и столбцы, элемент DataGridView готов к тому, чтобы пользователь или программа вводила значения в ячейки сформированной таблицы.

Рассмотрим теперь, как выглядит обработчик события "Click" следующей командной кнопки "Перенести данные в массив". Предполагается, что пользователь разумен и, прежде чем нажать эту кнопку, задает значения элементов перемножаемых матриц в соответствующих ячейках подготовленных таблиц первых двух элементов DataGridView. Обработчик события выполняет следующие задачи - в цикле читает элементы, записанные пользователем в таблицы DataGridView, проверяет их корректность и в случае успеха переписывает их в матрицы. Вот текст обработчика:

private void button2_Click(object sender, EventArgs e)
   {
       string elem = "";
       bool correct = true;
       for (int i = 0; i < m; i++)
           for (int j = 0; j < n; j++)
           {                    
              try
                {
                 elem=dataGridView1.Rows[i].Cells[j].Value.ToString();
                 A[i, j] = Convert.ToDouble(elem);
                 label8.Text = "";  
                 }
              catch (Exception any)
                 {
                   label8.Text = "Значение элемента" +
                  "A[" + i.ToString() +", " + j.ToString() + " ]"
                  + " не корректно. Повторите ввод!";
   dataGridView1.Rows[i].Cells[j].Selected= true;                                       
     return;
              }                   
           }
       for (int i = 0; i < n; i++)
           for (int j = 0; j < p; j++)
            {
               do
                {
                  correct = true;
                  try
                  {
              elem =
        dataGridView2.Rows[i].Cells[j].Value.ToString();                            
         B[i, j] = Convert.ToDouble(elem);
         label9.Text = "";
                      }
          catch (Exception any)
          {
            label9.Text = "Значение элемента" +
            "B[" + i.ToString() + ", " + j.ToString() + "]"
            + " не корректно. Повторите ввод!";
            dataGridView2.Rows[i].Cells[j].Selected=true;           
       Form3 frm = new Form3();
            frm.label1.Text = 
            "B[" + i.ToString() + "," + j.ToString() + "]= ";
            frm.ShowDialog();
         dataGridView2.Rows[i].Cells[j].Value = 
      frm.textBox1.Text;
            correct = false;
          }
                    } while (!correct);                     
                }
        }

Этот программный код нуждается в подробных комментариях.

Основная задача переноса данных из таблицы элемента DataGridView в соответствующий массив не вызывает проблем. Конструкция Rows[i].Cells[j] позволяет добраться до нужного элемента таблицы, после чего остается присвоить его значение элементу массива.

Как всегда при вводе основной проблемой является обеспечение корректности вводимых данных. Схема, рассматриваемая нами ранее, нуждается в корректировке. Дело в том, что ранее проверка корректности осуществлялась сразу же после ввода пользователем значения элемента. Теперь проверка корректности выполняется после того, как пользователь полностью заполнил таблицы, при этом некоторые элементы он мог задать некорректно. Просматривая таблицу, необходимо обнаружить некорректно заданные значения и предоставить возможность их исправления. В программе предлагаются два различных подхода к решению этой проблемы.

Первый подход демонстрируется на примере ввода элементов матрицы A. Как обычно, преобразование данных, введенных пользователем, в значение, допустимое для элементов матрицы А, помещается в охраняемый блок. Если данные некорректны и возникает исключительная ситуация, то она перехватывается универсальным обработчиком catch(Exception). Заметьте, в данном варианте нет цикла, работающего до тех пор, пока не будет введено корректное значение. Обработчик исключения просто прерывает работу по переносу данных, вызывая оператор return. Но предварительно он формирует информационное сообщение об ошибке и выводит его в форму. (Помните, специально для этих целей у формы были заготовлены две метки). В сообщении пользователю предлагается исправить некорректно заданный элемент и повторить ввод - повторно нажать командную кнопку "перенести данные в массив". Этот подход понятен и легко реализуем. Недостатком является его неэффективность, поскольку повторно будут переноситься в массив все элементы, в том числе и те, что были введены вполне корректно. У программиста такая ситуация может вызывать чувство неудовлетворенности своей работой.

На примере ввода элементов матрицы В продемонстрируем другой подход, когда исправляется только некорректно заданное значение. Прежде чем читать дальше, попробуйте найти собственное решение этой задачи. Это не так просто, как может показаться с первого взгляда. Для организации диалога с пользователем пришлось организовать специальное диалоговое окно, представляющее обычную форму с двумя элементами управления - меткой для выдачи информационного сообщения и текстовым окном для ввода пользователем корректного значения. При обнаружении ошибки ввода открывается диалоговое окно, в которое пользователь вводит корректное значение элемента и закрывает окно диалога. Введенное пользователем значение переносится в нужную ячейку таблицы DataGridView, а оттуда в матрицу.

При проектировании диалогового окна значение свойства формы FormBorderStyle, установленное по умолчанию как " sizeable ", следует заменить значением " FixedDialog ", что влияет на внешний вид и поведение формы. Важно отметить, что форма, представляющая диалоговое окно, должна вызываться не методом Show, а методом ShowDialog. Иначе произойдет зацикливание, начнут порождаться десятки диалоговых окон, прежде чем вы успеете нажать спасительную в таких случаях комбинацию Ctrl+ Alt + Del.

Обработчик события "Click" командной кнопки "Умножить матрицы" выполняет ответственные задачи - реализует умножение матриц и отображает полученный результат в таблице соответствующего элемента DataGridView. Но оба эти действия выполняются естественным образом, не требуя, кроме циклов, никаких специальных средств и программистских ухищрений. Я приведу программный код без дополнительных комментариев:

private void button3_Click(object sender, EventArgs e)
        {
            MultMatr(A, B, C);
            FillDG();          
        }
	void MultMatr(double[,] A, double[,] B, double[,] C)
        {
            int m = A.GetLength(0);
            int n = A.GetLength(1);
            int p = B.GetLength(1);
            double S =0;
            for(int i=0; i < m; i++)
                for (int j = 0; j < p; j++)
                {
                    S = 0;
                    for (int k = 0; k < n; k++)
                        S += A[i, k] * B[k, j];
                    C[i, j] = S;
                }
        }	
void FillDG()
        {
            for (int i = 0; i < m; i++)
                for (int j = 0; j < p; j++)
                    dataGridView3.Rows[i].Cells[j].Value
                        = C[i, j].ToString();
        }

Задачи (ввод, вывод и другие простые задачи с массивами)

1. Организуйте в консольном приложении ввод и вывод одномерного массива строкового типа.

2. Организуйте в Windows-приложении ввод и вывод одномерного массива строкового типа.

3. Организуйте в консольном приложении ввод массива "Сотрудники", содержащего фамилии сотрудников. Введите массив "Заявка", элементы которого содержат фамилии сотрудников и, следовательно, должны содержаться в массиве сотрудников. Обеспечьте контроль корректности ввода данных.

4. Организуйте в Windows-приложении ввод массива "Сотрудники", содержащего фамилии сотрудников. Введите массив "Заявка", элементы которого содержат фамилии сотрудников и, следовательно, должны содержаться в массиве сотрудников. Обеспечьте контроль корректности ввода данных.

5. Организуйте в Windows-приложении ввод массива "Сотрудники", содержащего фамилии сотрудников. Создайте массив "Заявка", элементы которого должны содержаться в массиве сотрудников. Для создания массива "Заявка" постройте форму "Два списка", содержащую два элемента ListBox, источником данных для первого из них служит массив "Сотрудники". Пользователь переносит данные из первого списка во второй, формируя данные для массива "Заявка". После формирования данные переносятся в массив. Для построения формы используйте шаблон, описанный в лекции 24 учебника.

6. Организуйте в консольном приложении ввод и вывод двумерного массива строкового типа.

7. Организуйте в Windows-приложении ввод и вывод двумерного массива строкового типа.

8. Организуйте в консольном приложении ввод массива "Сотрудники" из двух столбцов, содержащего фамилии и имена сотрудников. Введите массив "Заявка" той же структуры, элементы которого должны содержаться в массиве сотрудников. Обеспечьте контроль корректности ввода данных. Организуйте вывод обоих массивов.

9. Организуйте в Windows-приложении ввод массива "Сотрудники" из двух столбцов, содержащего фамилии и имена сотрудников. Введите массив "Заявка" той же структуры, элементы которого должны содержаться в массиве сотрудников. Обеспечьте контроль корректности ввода данных. Организуйте вывод обоих массивов.

10. (*) Организуйте в консольном приложении ввод и вывод массива "Машины", содержащего 4 столбца: "Владелец", "Марка", "Номер", "Год Выпуска". При вводе данных обеспечьте их корректность. Поле "Владелец" должно быть строкой в формате "фамилия имя", где фамилия и имя должны начинаться с большой буквы и состоять из букв алфавита кириллицы, включая дефис. Номер машины должен соответствовать формату, принятому для номеров машин. При выводе сохраняйте структуру массива.

11. (*) Организуйте в Windows-приложении ввод и вывод массива "Машины", содержащего 4 столбца: "Владелец", "Марка", "Номер", "Год Выпуска". При вводе данных обеспечьте их корректность. Поле "Владелец" должно быть строкой в формате "фамилия имя", где фамилия и имя должны начинаться с большой буквы и состоять из букв алфавита кириллицы, включая дефис. Номер машины должен соответствовать формату, принятому для номеров машин. При выводе сохраняйте структуру массива.

12. (*) В консольном приложении уже построен массив "Машины" (см. задача 3.9). Построить массив "Цветные машины", в котором к столбцам массива "Машины" добавляется 5-й столбец "Цвет". Организуйте диалог с пользователем, выясняя цвет для каждой машины из массива "Машины".

13. (*) В Windows-приложении уже построен массив "Машины" (см. задача 3.10) . Построить массив "Цветные машины", в котором к столбцам массива "Машины" добавляется 5-й столбец "Цвет". Организуйте диалог с пользователем, выясняя цвет для каждой машины из массива "Машины".

14. Организуйте в консольном приложении ввод и вывод одномерного массива арифметического типа (от byte до double).

15. Организуйте в Windows-приложении ввод и вывод одномерного массива арифметического типа (от byte до double).

16. Организуйте в консольном приложении ввод массива "Сотрудники", содержащего фамилии сотрудников, и массива "Зарплата". Обеспечьте контроль корректности ввода данных о зарплате, проверяя диапазон возможных значений.

17. Организуйте в Windows-приложении ввод массива "Сотрудники", содержащего фамилии сотрудников, и массива "Зарплата". Обеспечьте контроль корректности ввода данных о зарплате, проверяя диапазон возможных значений.

18. Организуйте в консольном приложении ввод и вывод матрицы - двумерного массива арифметического типа.

19. Организуйте в Windows-приложении ввод и вывод матрицы - двумерного массива арифметического типа.

20. Организуйте в консольном приложении ввод массива декартовых координат n точек на плоскости. Вычислите массив полярных координат этих точек и организуйте вывод этого массива. Обеспечьте контроль вводимых значений.

21. Организуйте в Windows-приложении ввод массива декартовых координат n точек на плоскости. Вычислите массив полярных координат этих точек и организуйте вывод этого массива. Обеспечьте контроль вводимых значений.

22. Организуйте в консольном приложении ввод массива полярных координат n точек на плоскости. Вычислите массив декартовых координат этих точек и организуйте вывод этого массива. Обеспечьте контроль вводимых значений.

23. Организуйте в Windows-приложении ввод массива полярных координат n точек на плоскости. Вычислите массив декартовых координат этих точек и организуйте вывод этого массива. Обеспечьте контроль вводимых значений.

24. Организуйте в консольном приложении ввод массива декартовых координат n точек в трехмерном пространстве. Вычислите массив полярных координат этих точек и организуйте вывод этого массива. Обеспечьте контроль вводимых значений.

25. Организуйте в Windows-приложении ввод массива декартовых координат n точек в трехмерном пространстве. Вычислите массив полярных координат этих точек и организуйте вывод этого массива. Обеспечьте контроль вводимых значений.

26. Организуйте в консольном приложении ввод и вывод массива декартовых координат n точек на плоскости. Вычислите массив, содержащий все комбинации из трех точек исходного массива, такие, что точки могут рассматриваться как вершины некоторого треугольника на плоскости. Организуйте вывод этого массива.

27. Организуйте в Windows-приложении ввод и вывод массива декартовых координат n точек на плоскости. Вычислите массив, содержащий все комбинации из трех точек исходного массива, такие, что точки могут рассматриваться как вершины некоторого треугольника на плоскости. Организуйте вывод этого массива.

Массивы и классические алгоритмы математики

Полиномы

Полиномом n-й степени $$P_n(x)$$ называют функцию:

$$P_n(x)=a_n x^n+a_{n-1}x^{n-1}+\ldots+a_1 x+a_0$$

Если рассматривать график этой функции на плоскости, то $$x$$ и $$P_n(x)$$ - это декартовы координаты точек графика функции. Значения $$a_k$$ (k из интервала [0,n]) называются коэффициентами полинома. Все они принадлежат одному типу и при программной работе с полиномами представляются одномерным массивом с n+1 элементами.

Если задан массив коэффициентов полинома $$A$$, то вычислить значение полинома в точке $$x$$ не представляет особой сложности. Но ни один уважающий себя программист не позволит себе вычислять значение полинома, буквально пользуясь схемой 6.1, требующей n-1 операций возведения в степень, n операций умножения и n операций сложения. Прекрасный пример того, как можно упростить алгоритм, дает схема Горнера, вообще не требующая возведения в степень. В этой схеме полином $$P_n(x)$$ представляют в виде:

$$P_n(x)=(\ldots(a_n)x+a_{n-1})x+\ldots+a_1)x+a_0$$

Удобнее представлять схему Горнера в рекуррентной форме:

$$P_0=a_n;\\ P_k=P_{k-1}x+a_{n-k};\quad k=1\ldots n$$

Вначале вычисляется значение полинома нулевой степени, состоящего из коэффициента при старшем члене исходного полинома. Затем рекуррентно повышается степень полинома, для чего достаточно умножить на x предыдущее значение и добавить новый коэффициент. В программе эта схема естественным образом реализуется обычным циклом, где на каждом шаге выполняется одно умножение и одно сложение.

Если $$P_n(x)$$ - полином n-й степени с коэффициентами $$a_i$$, $$Q_n(x)$$ - полином n-й степени с коэффициентами $$b_i$$ и $$P_n(x) = Q_n(x)$$, то из этого следует равенство соответствующих коэффициентов:

$$(P_n(x)=Q_n(x))\Rightarrow(a_i=b_i;\; \forall_i=0\ldots n)$$

Многие задачи над полиномами связаны с определением их корней. Напомню, $$x_0$$ является корнем полинома, если $$P_n(x_0) = 0$$. У полинома n-й степени не более чем $$n$$ действительных корней. Если $$n$$ - нечетно, то полином имеет хотя бы один действительный корень. Все корни полинома принадлежат некоторому конечному интервалу [c, d]. Вне этого интервала поведение полинома определяется его старшим членом - $$a_n x^n$$. Для полинома четной степени обе ветви уходят в $$+\infty$$, если $$a_n >0$$ и в $$-\infty$$, если $$a_n<0$$. Для полинома нечетной степени ветви полинома вне интервала [c, d] разнонаправлены. Если $$a_n>0$$, то правая ветвь уходит в $$+\infty$$, а левая ветвь - в $$-\infty$$. Если $$a_n<0$$, то левая ветвь уходит в $$+\infty$$, а правая ветвь - в $$-\infty$$.

Когда по каким-либо физическим соображениям интервал [c, d] известен хотя бы приблизительно, задача нахождения корней полинома облегчается, в противном случае она может быть довольно трудной, особенно для случая близко расположенных корней.

Исследование интервала

Рассмотрим один из простых алгоритмов, исследующих, существует ли на заданном интервале [e, f] хотя бы один корень. Один корень заведомо существует, если полином на концах исследуемого интервала имеет разные знаки или один из концов интервала уже является корнем полинома. Это условие и будет характерным признаком поиска нужного интервала. Если исходный интервал [e, f] удовлетворяет характерному признаку, то задача решена и такой интервал найден. В противном случае в цикле по $$k$$ вычислим $$h = L/2^k$$, где $$L$$ - длина исходного интервала ( $$L= f-e$$ ). Затем организуем внутренний цикл, в котором проверим характерный признак на всех интервалах длины h. Если интервал будет найден, то вычисления завершаются, в противном случае переходим к следующему шагу цикла по $$k$$, производя очередное дробление $$h$$. Завершение цикла по $$k$$ означает, что если исследуемый интервал [e, f] и содержит корни, то это близкие пары корней, отстоящие друг от друга на расстояние, меньшее $$h$$ - заключительной длины интервала по завершении цикла по $$k$$.

Приведу несколько практических рекомендаций, полезных при реализации этой схемы. Внутренний цикл следует организовать так, чтобы не повторять вычисление полинома в тех точках, в которых это вычисление проводилось на предыдущих шагах цикла. Это означает, что когда шаг $$h = L/2^k$$, то во внутреннем цикле достаточно вычислить значение полинома не более чем в $$2^{k-1}$$ точках. Внешний цикл достаточно ограничить числом в интервале от 10 до 20, поскольку уже при $$k=10$$ величина исходного интервала $$L$$ уменьшится более чем в 1000 раз, что вполне достаточно в большинстве практических ситуаций. Хотя следует помнить, что в ряде ситуаций практики приходится иметь дело с резко осциллирующими функциями, где близкие корни являются правилом, а не исключением.

Алгоритмы нахождения корня полинома

Рассмотрим несколько простых схем нахождения корня полинома. Заметим, что все эти схемы применимы к нахождению корней любых функций, а не только полиномов. Как всегда в программировании, речь идет не столько о точном нахождении корня, сколько о нахождении корня с заданной точностью $$\varepsilon$$. Так что, если $$x_0$$ - это точное значение корня, то нам достаточно найти $$x*$$ - такое, что $$|x_0 - x*| < \varepsilon$$.

Схема дихотомии отрезка (деление пополам)

Эта схема прекрасно подходит, когда предварительно проведено исследование интервала существования корня и найден такой интервал [e, f], на концах которого полином принимает разные знаки, так что существует корень внутри интервала. Если исходный интервал мал и сравним с заданной точностью $$\varepsilon$$, то в качестве корня можно выбрать середину этого интервала. Если же исходный интервал больше, чем значение $$\varepsilon$$, то интервал можно разделить пополам и из двух половинок выбрать ту, для которой выполняется характерный признак существования корня. Понятно, что если признак выполняется для всего интервала, то он обязательно будет выполняться для одной из его половинок. Деление отрезка пополам приводит к быстрому уменьшению длины отрезка, так что 10-20 делений достаточно, чтобы найти интервал длины, меньшей $$\varepsilon$$, а следовательно, и корень полинома с заданной точностью.

Метод простой итерации

Формально метод применим и в том случае, когда неизвестен интервал, в котором существует корень функции. Пусть $$x_0$$ - некоторое заданное начальное приближение к корню полинома. Тогда можно построить следующий итерационный процесс:

$$x_k=x_{k-1}-f(x_{k-1});\quad k=1,2,\ldots$$

Метод записан для произвольной функции $$f$$, в нашем случае функция $$f$$ задана полиномом. Итерационный процесс следует прекращать либо по достижении заданной точности, либо по достижении максимально допустимого числа итераций $$N$$. Заметьте, следует задавать оба условия, поскольку сходимость процесса простой итерации к корню, даже если он существует, не гарантируется. Во многом все зависит от удачного выбора начального приближения.

Метод простой итерации обладает полезным свойством "неподвижной точки". Корни функции являются "неподвижными точками" метода. Нетрудно заметить, что если на некотором шаге $$x_{k-1}$$ сошлось к корню полинома $$x*$$, то $$x_k$$ и все последующие итерации будут равны $$x*$$, так что итерационный процесс из найденного корня не уходит.

Метод Ньютона

Этот метод чуть более сложен в реализации, но обладает лучшей сходимостью в сравнении с методом простой итерации, хотя и здесь сходимость во многом зависит от удачного выбора начального приближения $$x_0$$. Для произвольной функции $$f$$ итерационный процесс метода Ньютона выглядит так:

$$x_k=x_{k-1}-\frac{f(x_{k-1})}{f'(x_{k-1})};\quad k=1,2,\ldots$$

Понятно, что производной от полинома n-й степени будет полином степени n-1, коэффициенты которого легко вычисляются по n и коэффициентам исходного полинома. Все, что было сказано о методе простой итерации - завершение процесса, обладание неподвижной точкой, - справедливо и для метода Ньютона.

Понижение степени полинома

Если для полинома $$P(x)$$ n-й степени найден корень $$x_1$$, то можно понизить степень полинома, построив полином $$P1(x)$$ степени $$n-1$$, у которого все корни совпадают с корнями полинома $$P(x)$$ за исключением того, что у него нет корня $$x_1$$.

Запишем соотношение, связывающее полиномы:

$$P(x)=P1(x)(x-x1)\\ a_n x^n+a_{n-1}x^{n-1}+\ldots+a_1 x+a_0=(b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\ldots+b_1 x+b_0)(x-x1)$$

Учитывая соотношение 6.3 о равенстве двух полиномов одной степени, можно выписать $$n+1$$ соотношение, связывающее коэффициенты этих полиномов. Эти соотношения нетрудно разрешить относительно неизвестных коэффициентов $$b_k$$. В результате получим:

$$b_{n-1}=a_n;\\ b_{n-2}=a_{n-1}+b_{n-1}x_1;\\ \ldots\\ b_0=a_1+b_1 x_1;$$

Заметьте, неизвестных всего $$n$$, а уравнений можно построить - $$n+1$$. Но последнее уравнение $$(a0 + b_0 x1 = 0)$$ является следствием предыдущих и используется для контроля вычислений.

К новому полиному можно применить тот же процесс - найти его корень и понизить затем степень полинома. Реально понижение степени не намного упрощает задачу отыскания корней, так что чаще всего проще искать корни исходного полинома, изменяя начальные приближения в итерационном процессе или отыскивая различные интервалы, на которых полином меняет свой знак.

Нахождение коэффициентов полинома по его корням

До сих пор рассматривалась задача отыскания корней полинома с заданными коэффициентами. Иногда приходится решать обратную задачу - найти коэффициенты полинома, если известны его корни - $$x_1, x_2, … x_n$$. Полиномов с одинаковыми корнями существует бесчисленное множество. Однако среди них существует единственный полином с коэффициентом $$a_n$$, равным единице. Этот полином называется приведенным, его-то и будем строить. Все остальные полиномы получаются из приведенного полинома умножением всех коэффициентов на произвольное число $$a_n$$, от которого требуется лишь, чтобы оно не было равно нулю. Поэтому для однозначного решения задачи требуется задать n корней и коэффициент при старшем члене полинома. Тогда можно записать следующее равенство:

$$P_n(x)=a_n(x-x_n)(x-x_{n-1})\ldots(x-x_1)$$

Для нахождения коэффициентов полинома $$P_n(x)$$ воспользуемся, как обычно, соотношением 6.3. Но применить его напрямую сложно. Поэтому воспользуемся процессом, обратным к процессу понижения степени. Построим вначале $$P_1(x)$$ - полином первой степени, у которого $$x_1$$ является единственным корнем. Затем повысим степень и построим полином второй степени - $$P_2(x)$$, у которого появляется еще один корень - $$x_2$$. Продолжая этот процесс, дойдем до искомого полинома $$P_n(x)$$. При вычислении коэффициентов нового полинома будем использовать коэффициенты уже посчитанного полинома на единицу меньшей степени. Получающиеся в результате соотношения близки к тем, что приведены для случая понижения степени полинома.

Коэффициенты полинома первой степени $$P_1(x)$$ выписываются явно:

$$a_1=1;\quad a_0=-x_1;$$

Коэффициенты полинома k-й степени вычисляются через коэффициенты полинома степени k-1:

$$P_k(x)=P_{k-1}(x)(x-x_k)$$

Переходя к коэффициентам, получим следующие уравнения:

$$a_k=a'_{k-1};\\ a_{k-i}=a'_{k-i-1}-a'_{k-i}x_k;\quad \forall i\quad i=1,\dots k-1;\\ a_0=-a'_0 x_k;$$

В соотношении 6.5 через $$a'$$ обозначены коэффициенты полинома степени $$k-1$$. На самом деле схема безопасна и позволяет считать коэффициенты на том же месте, не требуя дополнительной памяти. Приведу алгоритм вычисления коэффициентов полинома по его корням в виде схемы, приближенной к языку C#.

Дано:

$$an$$ - коэффициент при старшем члене полинома $$P_n(x)$$ ;

$$n$$ - степень полинома;

$$x$$ - массив корней полинома $$(x[0], x[1], …x[n])$$ ;

Вычислить:

массив $$a$$ - массив коэффициентов полинома $$(a[0], a[1], …a[n])$$.

//Вычисляем коэффициенты полинома первой степени
a[1]= 1;	a[0] = -x[0];
//цикл по числу полиномов
for(int k=2;k<=n; k++)
{
	//Вычисляем коэффициенты полинома степени k
	//Вначале старший коэффициент
	a[k]= a[k-1];
	//затем остальные коэффициенты, кроме последнего
	for(int i=k-1;i>0; i--)
	{
  a[i] = a[i-1]- a[i]*x[k-1];
	}
	//теперь младший коэффициент
	a[0]= -a[0]*x[k-1];
}
//Последний этап - умножение коэффициентов на an
for(int i=0; i<=n; i++)
	a[i] = a[i]*an;

Полином Лагранжа

Пусть на плоскости заданы $$n+1$$ точка: $$R_0(x_0, y_0), R_1(x_1, y_1), R_2(x_2, y_2),\ldots, R_n(x_n, y_n)$$. Полиномом Лагранжа $$P_L(x)$$ называется полином n-й степени, проходящий через все точки $$R_k$$. Если точки $$R_k$$ не образуют возвратов, то такой полином существует и является единственным. Под возвратом понимается ситуация, когда существуют две точки $$R_i$$ и $$R_j$$ такие, что $$x_i = x_j$$.

Как построить такой полином? Лагранж предложил следующий алгоритм. Полином $$P_L(x)$$ строится как сумма $$n+1$$ полиномов n-й степени:

$$P_L(x)=\sum\limits_{k=1}^{n+1}P_k(x)$$

Каждый из полиномов $$P_k(x)$$, входящих в сумму, строится следующим образом. Корнями полинома $$P_k(x)$$ являются все точки $$R_i$$ за исключением точки $$R_k$$. Единственность $$P_k(x)$$ обеспечивается за счет того, что коэффициент при старшем члене an подбирается так, чтобы полином проходил через точку $$R_k$$. В записи Лагранжа полином $$P_k(x)$$ выглядит следующим образом:

$$P_k(x)=y_k\frac{(x-x_o)(x-x_1)\ldots(x-x_{k-1})(x-x_{k+1})\ldots(x-x_n)}{(x_k-x_0)(x_k-x_1)\ldots(x_k-x_{k-1})(x_k-x_{k+1})\ldots(x_k-x_n)}$$

В записи 6.6 в числителе находится приведенный полином, построенный по корням, а $$y_k$$, деленное на знаменатель в формуле 6.6, задает $$an$$ - старший коэффициент полинома.

Условия, накладываемые на полиномы $$P_k(x)$$, обеспечивают выполнение требований к полиному Лагранжа - сумма полиномов $$P_k(x)$$ будет полиномом, проходящим через все заданные точки.

Поскольку алгоритм построения приведенного полинома по его корням уже разобран, то схема построения полинома Лагранжа может выглядеть так:

//Полином Лагранжа определяется как сумма из n+1
//полиномов Pk, для которых известны корни.  
for(int k=0; k<=n; k++)
  	{    
    //Задание корней для полинома Pk  
    for(int i =0; i<k; i++)
    	roots[i] = X[i];
    for(int i =k+1; i<=n; i++)
    	roots[i-1] = X[i];
    //Вычисление коэффициентов приведенного полинома по его корням
    coefk = CalcCoefFromRoots(roots);               
         //вычисление An - старшего коэффициента полинома.
     An = Y[k] / HornerP(coefk,X[k]);
    //Добавление очередного полинома Pk к PL - сумме полиномов
    for(int i =0; i<=n; i++)
    {
    	coefL[i]= coefL[i]+An*coefk[i];
    }
  	}

В этой схеме:

X и Y - массивы, задающие декартовы координаты точек, через которые проходит полином Лагранжа,

n - степень полинома,

roots - массив корней приведенного полинома $$P_k$$,

coefk - массив его коэффициентов,

An - старший коэффициент полинома, вычисляемый из условия прохождения полинома $$P_k$$ через точку с координатами X[k], Y[k],

coefL - массив коэффициентов полинома Лагранжа,

HornerP - метод, вычисляющий по схеме Горнера значение полинома по его коэффициентам и значению координаты x,

CalcCoefFromRoots - метод, вычисляющий массив коэффициентов приведенного полинома по его корням.

Сложение и умножение полиномов

При рассмотрении полинома Лагранжа возникала необходимость в нахождении суммы полиномов одинаковой степени, заданных своими коэффициентами. Пусть P(x) и Q(x) - полиномы степени n и m, соответственно, заданные своими коэффициентами, и пусть для определенности $$n >= m$$. Тогда суммой полиномов называется полином R(x) степени n, коэффициенты которого вычисляются следующим образом:

$$R(x)=P(x)+Q(x)\Rightarrow \sum\limits_{i=0}^n c_i x^i=\sum\limits_{i=0}^n a_i x^i+\sum\limits_{i=0}^m b_i x^i\Rightarrow\\ c_i=a_i+b_i\quad \forall i<=m;\\ c_i=a_i\quad \forall i:m<i<=n;$$

Пусть полиномы P(x) и Q(x) заданы, подобно полиному Лагранжа, точками, через которые они проходят:

$$P(x):\{(px_0,py_0),(px_1,py1),\ldots(px_n,py_n)\}\\ Q(x):\{(qx_0,qy_0),(qx_1,qy1),\ldots(qx_m,qy_m)\}$$

Тогда нетрудно найти подобное представление и для полинома R(x), представляющего сумму полиномов:

$$R(x):\{(rx_0,ry_0),(rx_1,ry1),\ldots(rx_n,ry_n)\},\quad\text{где}\\ rx_i=px_i;\quad ry_i=py_i+Q(px_i);$$

В этом случае понадобится вычислить значения полинома Q(x) в n точках.

Если полиномы P(x) и Q(x) заданы своими корнями, то определить корни полинома суммы не удается, более того, у суммы вообще может не быть корней. В этом случае для каждого полинома по корням можно вычислить коэффициенты, а затем определить коэффициенты полинома суммы. Можно также рассматривать корни как частный случай задания множества точек, через которые проходит полином, и применить предыдущую схему для определения множества точек, через которые проходит полином суммы.

Рассмотрим теперь операцию умножения полиномов:

$$S(x)=P(x)*Q(x)$$

Нетрудно понять, что полином S(x) является полиномом степени $$n+m$$ и имеет $$n+m+1$$ коэффициент. Как вычисляется произведение, если заданы полиномы сомножители P(x) и Q(x)? Замечу, что произведение полиномов часто встречается на практике и имеет специальное имя - свертка полиномов.

В отличие от сложения полиномов проще всего найти свертку, если заданы корни обоих полиномов. В этом случае никаких вычислений не требуется, поскольку n корней P(x) и m корней Q(x) будут $$n+m$$ корнями S(x). Если у полиномов P(x) и Q(x) есть совпадающие корни, то у S(x) появятся кратные корни.

Если исходные полиномы P(x) и Q(x) заданы своими точками, то нетрудно получить набор точек для полинома произведения. Схема во многом похожа на ту, что имеет место при сложении полиномов, заданных точками:

$$S(x)=\{(sx_0,sy_0),(sx_1,sy_1),\ldots(sx_{n+m},sy_{n+m})\},\quad\text{где}\\ sx_i=px_i;\quad sy_i=py_i*Q(px_i)\quad \forall i:i<=n;\\ sx_i=qx_{i-n-1};\quad sy_i=qy_{i-n-1}*P(qx_{i-n-1})\quad \forall i:n<i<=n+m+1$$

Для получения множества точек, задающих представление полинома S(x), приходится вычислять значение полинома Q(x) в n точках и значение полинома P(x) в m точках, а затем выполнять соответствующее умножение значений двух полиномов.

Если исходные полиномы P(x) и Q(x) заданы своими коэффициентами, то имеем:

$$S(x)=P(x)*Q(x)=(\sum\limits_{i=0}^n a_i x^i)*(\sum\limits_{j=0}^m b_j x^j)$$

Каждый член первой суммы приходится умножать на все члены второй суммы и затем приводить подобные члены при одинаковых степенях x. Нетрудно заметить, что в результате коэффициенты полинома S(x) определяются следующими соотношениями:

$$S(x)=\sum\limits_{i=0}^{n+m}d_i;\quad\text{где}\\ d_i=\sum\limits_{k+r=i}a_k b_r;\quad k\in[0,n];\quad r\in[0,m]$$

Суммирование идет по всем наборам k и r, дающим в сумме значение i. Понятно, что для крайних значений (i=0 и i=n+m) сумма состоит из одного члена, поскольку подобные члены для x в нулевой степени и степени n+m отсутствуют. Число членов суммирования увеличивается при приближении к середине интервала [0, n+m].

Итоги

Подводя некоторые итоги, отметим, что полином можно задать тремя разными способами - его коэффициентами, корнями и точками, через которые проходит полином. Если заданы коэффициенты полинома, то за время, пропорциональное $$n^2, (T(n) = O(n^2))$$ можно вычислить значения полинома в n+1 точках. Для вычисления значения полинома в одной точке применяется схема Горнера, выполняющая вычисления за линейное (пропорциональное n) время. Существует и обратное преобразование. Если заданы n+1 точки, через которые проходит полином, то алгоритм Лагранжа позволяет за время $$O(n^2)$$ вычислить коэффициенты полинома. Задача получения коэффициентов полинома по точкам называется задачей интерполяции, а полином Лагранжа называется интерполяционным полиномом.

Если заданы корни, то можно получить два других представления. Рассмотренный нами алгоритм позволяет по корням полинома за время $$O(n^2)$$ вычислить коэффициенты полинома. Алгоритм использует итеративную схему из n шагов, где на каждом шаге выполняется операция повышения степени, выполняемая за линейное время. Поскольку корни являются частным случаем задания множества точек, через которые проходит полином, то задание корней автоматически задает и представление полинома набором точек. Обратная задача - получение корней по коэффициентам или заданным точкам - так просто не решается. Точное ее решение существует для полиномов второй и третьей степени, но не в общем случае. Для нахождения корней приходится использовать приближенные итеративные методы, например, метод простой итерации или Ньютона.

Задание полинома его корнями является наиболее информативным. Если известны корни, то без труда выполняется свертка полиномов. Вычисление значения полинома в заданной точке выполняется за n умножений, не требуя применения схемы Горнера. Несколько сложнее выполняется операция сложения полиномов. К сожалению, на практике редко встречается ситуация, когда известны корни полинома, но такое бывает - алгоритм Лагранжа тому пример.

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

На практике полиномы чаще всего появляются при задании множества точек. Ситуация обычно такова. В результате экспериментов измеряются значения некоторой функции в ряде точек. Требуется предсказать, каково будет значение этой функции в других точках, в которых измерения не проводились. Если из теоретических соображений не известен вид функции, то чаще всего ее задают в виде полинома, проходящего через точки, полученные экспериментальным путем. В этой постановке задачу построения полинома и вычисления значений полинома в точках, не подлежащих измерениям, называют задачей интерполяции, а полином Лагранжа называют интерполяционным полиномом. Задача интерполяции корректно решается, когда новые точки, в которых проводятся вычисления, лежат внутри интервала, заданного измеренными точками. Полиномы плохо приспособлены для решения задачи экстраполяции, когда точки лежат вне интервала измерений, из-за быстрого роста значения полинома вне этого интервала. Чем выше степень полинома, тем быстрее его рост.

Множество точек, через которые проходит полином, обычно несет дополнительную информацию. Некоторые точки, например, могут быть корнями полинома или задавать интервалы, внутри которых находятся корни.

Одно замечание к задаче свертки полиномов. Приведенный алгоритм решения этой задачи для полиномов, заданных своими коэффициентами, требует квадратичного времени. Ввиду практической важности этой задачи много внимания уделялось поиску наиболее эффективного по временной сложности алгоритма. Существуют алгоритмы, решающие эту задачу за время $$O(n*log(n))$$. Эти алгоритмы используют технику быстрого преобразования Фурье и обратного к нему. Они сложнее в реализации и требуют работы с комплексными числами или выполнения операций модульной арифметики. Здесь они только упоминаются и детально не рассматриваются.

Задачи

В задачах этого раздела уже не говорится о том, какого типа проект следует строить - консольный или Windows. Предполагается, что обычной практикой является построение Windows-приложений.

28. Полином P(x) задан своими коэффициентами. Дан массив координат X. Вычислить, используя схему Горнера, массив значений полинома в точках $$x_i$$.

29. Полином P(x) задан своими корнями и старшим коэффициентом an. Дан массив координат X. Вычислить массив значений полинома в точках $$x_i$$.

30. (задача интерполяции) Полином P(x) задан координатами n+1 точек, через которые он проходит. Дан массив координат X. Вычислить массив значений полинома в точках $$x_i$$.

31. Полином P(x) задан своими корнями и старшим коэффициентом an. Вычислить коэффициенты полинома.

32. (задача построения интерполяционного полинома Лагранжа) Полином P(x) задан координатами n+1 точек, через которые он проходит. Вычислить коэффициенты полинома.

33. Полином P(x) задан своими коэффициентами. Дан массив чисел X. Построить полином Q(X), имеющий своими корнями числа из массива X и корни полинома P(x).

34. Полином P(x) задан своими коэффициентами. Для полинома известны два его корня - x0 и xn. Построить полином Q(x), корни которого совпадают с корнями полинома P(x), за исключением корней x0 и xn.

35. Полиномы P(x) и Q(x) заданы своими корнями и старшими коэффициентами. Вычислить коэффициенты суммы полиномов P(x) и Q(x).

36. Полиномы P(x) и Q(x) заданы своими корнями и старшими коэффициентами. Вычислить коэффициенты произведения полиномов P(x) и Q(x).

37. Полиномы P(x) и Q(x) заданы своими коэффициентами. Вычислить коэффициенты суммы полиномов P(x) и Q(x).

38. Полиномы P(x) и Q(x) заданы своими коэффициентами. Вычислить коэффициенты произведения полиномов P(x) и Q(x).

39. Полиномы P(x) и Q(x) заданы точками, через которые они проходят. Вычислить коэффициенты суммы полиномов P(x) и Q(x).

40. Полиномы P(x) и Q(x) заданы точками, через которые они проходят. Вычислить коэффициенты произведения полиномов P(x) и Q(x).

41. Полином P(x) задан своими коэффициентами. Определить интервал, если он существует, на котором полином имеет хотя бы один корень.

42. Полином P(x) задан точками, через которые он проходит. Определить интервал, если он существует, на котором полином имеет хотя бы один корень.

43. Для полинома P(x), заданного своими коэффициентами, известен интервал, на котором полином имеет хотя бы один корень. Найти корень с заданной точностью, используя схему дихотомии.

44. Построить интерфейс пользователя, позволяющий ему находить корни полинома. В основу поиска положить схему исследования интервала и дихотомии.

45. Построить интерфейс пользователя, позволяющий ему находить корни полинома. В основу поиска положить метод простой итерации.

46. Построить интерфейс пользователя, позволяющий ему находить корни полинома. В основу поиска положить метод Ньютона.

Проект

47. Построить проект, включающий построение интерфейса пользователя и класса Polinom. Методы класса должны реализовать все алгоритмы, рассмотренные в этом разделе. Интерфейс пользователя должен позволять пользователю решать основные задачи, возникающие при работе с полиномами.

Алгоритмы линейной алгебры

Матрицей называется набор чисел, состоящий из m строк и n столбцов. Для программиста матрица - это двумерный массив. Матрица называется квадратной, если m = n, и прямоугольной - в противном случае. Числа m и n определяют размерность матрицы. Над прямоугольными матрицами определены операции транспонирования, сложения, умножения.

Пусть A - матрица размерности m*n (из m строк и n столбцов) с элементами $$a_{i,j}$$. Транспонированной матрицей B = AT называют матрицу размерности n*m, элементы которой $$b_{i,j} = a_{j,i}$$. В транспонированной матрице строки исходной матрицы становятся столбцами.

$$A=\left|\left|\begin{array}{l}a_{1,1},a_{1,2}\ldots a_{1,n}\\ a_{2,1},a_{2,2}\ldots a_{2,n}\\ \ldots\\ a_{m,1},a_{m,2}\ldots a_{m,n}\end{array}\right|\right| \quad B=A^T=\left|\left|\begin{array}{l}a_{1,1},a_{2,1}\ldots a_{m,1}\\ a_{1,2},a_{2,2}\ldots a_{m,2}\\ \ldots\\ a_{1,n},a_{2,n}\ldots a_{m,n}\end{array}\right|\right|$$

Операция сложения определена над прямоугольными матрицами одинаковой размерности. Пусть A, B, C - прямоугольные матрицы размерности m*n. Тогда сумма матриц определяется естественным образом:

$$A=\left|\left|\begin{array}{l}a_{1,1},a_{1,2}\ldots a_{1,n}\\ a_{2,1},a_{2,2}\ldots a_{2,n}\\ \ldots\\ a_{m,1},a_{m,2}\ldots a_{m,n}\end{array}\right|\right| \quad B=\left|\left|\begin{array}{l}b_{1,1},b_{1,2}\ldots b_{1,n}\\ b_{2,1},b_{2,2}\ldots b_{2,n}\\ \ldots\\ b_{m,1},b_{m,2}\ldots b_{m,n}\end{array}\right|\right|\\ C=A+B=\left|\left|\begin{array}{l}a_{1,1}+b_{1,1},a_{1,2}+b_{1,2}\ldots a_{1,n}+b_{1,n}\\ a_{2,1}+b_{2,1},a_{2,2}+b_{2,2}\ldots a_{2,n}+b_{2,n}\\ \ldots\\ a_{m,1}+b_{m,1},a_{m,2}+b_{m,2}\ldots a_{m,n}+b_{m,n}\end{array}\right|\right|$$

Операция умножения определена над прямоугольными матрицами, у которых число столбцов первого сомножителя равно числу строк второго сомножителя. Матрица произведения имеет число строк, равное числу строк первого сомножителя, и число столбцов, равное числу столбцов второго сомножителя. Пусть A - матрица размерности m*p, B - размерности p*n, тогда матрица C= A*B имеет размерность m*n. Элементы матрицы произведения определяются как сумма попарных произведений элементов строки первого сомножителя на элементы столбца второго сомножителя.

$$A=\left|\left|a_{i,j}\right|\right|\quad i=1,...m;\;j=1,...p;\quad B=\left|\left|b_{j,k}\right|\right|\quad j=1,...p;\;k=1,...n\\ C=A*B=\left|\left|c_{i,k}\right|\right|\quad i=1,...m;\;k=1,...n;\\ c_{i,k}=\sum\limits_{j=1}^p a_{i,j}*b_{j,k};$$

Умножение всегда определено для прямой и транспонированной матрицы. Если A - прямоугольная матрица размерности m*n, то всегда определена квадратная матрица B размерности m*m:

$$B = A*A^T = B^T = (A*A^T)^T = (A^T)^T*A^T= A*A^T$$

Результатом такого произведения является симметричная матрица. Квадратная матрица называется симметричной, если $$a_{i,j} = a_{j,i}$$ для всех i и j, или, что то же, если $$A = A^T$$. Операции транспонирования, сложения и умножения обладают следующими свойствами:

$$(A^T)^T=A;\quad (A+B)^T=A^T+B^T;\quad (A*B)^T=B^T*A^T$$

Квадратные матрицы

Квадратная матрица называется диагональной, если все элементы, кроме диагональных, равны нулю, то есть $$a_{i,j} = 0$$ при $$i /=j$$.

Квадратная матрица называется единичной, если все элементы, кроме диагональных, равны нулю, а диагональные элементы равны единице, то есть $$a_{i,j} = 0$$ при $$i /=j$$ и $$a_{i,j} = 1$$ при $$i = j$$. Единичная матрица обозначается обычно буквой E, и она играет роль единицы при умножении матриц, поскольку для любой квадратной матрицы A и единичной матрицы E той же размерности имеют место соотношения:

$$A*E = E*A = A$$

Для квадратных матриц определена функция над ее элементами, называемая определителем. Обозначается определитель обычно с помощью одинарных линий вокруг набора чисел, задающих матрицу:

$$D(A)=\left|\begin{array}{l}a_{1,1},a_{1,2}\ldots a_{1,n}\\ a_{2,1},a_{2,2}\ldots a_{2,n}\\ \ldots\\ a_{n,1},a_{n,2}\ldots a_{n,n}\end{array}\right|$$

Функция, задающая определитель, обладает рядом важных свойств.

Определитель диагональной матрицы равен произведению диагональных элементов. Отсюда следует, что определитель матрицы E равен 1.

Определитель матрицы не меняется при выполнении над матрицей элементарных преобразований. Под элементарной операцией (преобразованием) понимается прибавление к любой строке матрицы линейной комбинации других ее строк. В частности, если к строке матрицы с номером j прибавить строку с номером $$k (k /= j)$$, умноженную на некоторое число, то определитель матрицы не изменится.

Если все элементы одной строки матрицы умножить на некоторое число q, то определитель матрицы изменится в q раз (умножается на q).

Если переставить местами строки j и k, то модуль определителя не изменится, но изменится знак, если разность $$|k-j|$$ является нечетным числом.

Определитель произведения матриц равен произведению определителей:$$D(A*B) = D(A)*D(B)$$

Не приводя общего формального определения, рассмотрим ниже алгоритм вычисления определителя матрицы, основанный на его свойствах.

Если определитель квадратной матрицы A не равен нулю, то существует обратная матрица, обозначаемая как $$A^{-1}$$. Прямая и обратная матрицы связаны соотношением:

$$A*A^{-1} = A^{-1}*A = E$$

Операции транспонирования, умножения и обращения матриц связаны соотношениями:

$$(A^T)^{-1} = (A^{-1})^T;\quad (A*B)^{-1} = B^{-1}*A^{-1}$$

Множество квадратных матриц одной размерности с определителем, отличным от нуля образуют группу по умножению. В группе есть единичный элемент, для каждого элемента существует обратный к нему, и произведение элементов принадлежит группе.

Иногда полезно рассматривать матрицу, состоящую не из элементов, а из клеток, каждая из которых является матрицей. Все определения операций над матрицами, элементы которых являются числами, переносятся на матрицы, элементы которых являются клетками. Такое представление особенно полезно для разреженных матриц, где большинство элементов являются нулями. Тогда можно представить такую матрицу как клеточную матрицу, многие клетки которой равны нулю. Используя знание структуры подобных матриц, можно в результате существенно сократить объем вычислений. Рассмотрим простой пример умножения двух матриц размерности 100*100, каждая из которых задана в виде четырех клеток:

$$A=\left|\left|\begin{array}{lr}A(20*40)B(20*60)\\ C(80*40)D(80*60)\end{array}\right|\right|\quad M1=\left|\left|\begin{array}{lr}E(40*70)F(40*30)\\ G(60*70)H(60*30)\end{array}\right|\right|\\ M2=M*M1=\left|\left|\begin{array}{lr}A*E+B*GA*F+B*H\\ C*E+D*GC*F+D*H\end{array}\right|\right|$$

В круглых скобках для клеток заданы их размерности. Пусть теперь некоторые клетки нулевые, например, таковыми являются клетки D, F и G. Тогда матрица M2 имеет вид:

$$M2=\left|\left|\begin{array}{cc}A*EB*H\\ C*E0\end{array}\right|\right|$$

Для вычисления матрицы M2 необходимо будет найти произведение трех пар матриц, но значительно меньших размеров, чем исходные матрицы. В целом объем вычислений сократится более чем в три раза.

Иногда приходится иметь дело с треугольными матрицами, у которых все элементы выше или ниже диагонали равны нулю. Квадратную матрицу будем называть нижнетреугольной, если все элементы выше главной диагонали равны нулю, и верхнетреугольной, если равны нулю все элементы ниже главной диагонали.

Системы линейных уравнений

Рассмотрим систему из n линейных уравнений с n неизвестными:

$$a_{1,1}x_1+a_{1,2}x_2+\ldots+a_{1,n}x_n=b_1\\ a_{2,1}x_1+a_{2,2}x_2+\ldots+a_{2,n}x_n=b_2\\ \ldots\\ a_{n,1}x_1+a_{n,2}x_2+\ldots+a_{n,n}x_n=b_n$$

В матричном виде эта система записывается намного элегантнее:

$$A*x=b$$

Здесь вектор неизвестных x рассматривается как столбец - прямоугольная матрица размерности n*1. Аналогичный вид имеет вектор правых частей b системы уравнений. В матричном виде условие существования решения системы линейных уравнений 6.8 и нахождение самого решения формулируется совсем просто. Для существования решения необходимо и достаточно, чтобы определитель матрицы A был отличен от нуля. Тогда у матрицы A существует обратная матрица $$A^{-1}$$. Для нахождения решения системы умножим обе части уравнения 6.9 на $$A^{-1}$$. Тогда получим:

$$A^{-1}*(A*x) = A^{-1}*b\quad \to(A^{-1}*A)*x = A^{-1}*b\quad \to(E)*x = A^{-1}*b\quad \to x = A^{-1}*b$$

Для нахождения решения системы линейных уравнений, матрица которой имеет определитель, отличный от нуля, достаточно вычислить обратную матрицу и умножить ее на вектор правых частей системы уравнений.

Если нужно решить m систем линейных уравнений с одной и той же матрицей $$A$$, но с разными правыми частями, то обратную матрицу достаточно вычислить один раз. В матричном виде решение m систем линейных уравнений

$$A*X = B$$

задается соотношением:

$$X = A^{-1}*B$$

Здесь $$B$$ - прямоугольная матрица размерности $$n*m$$, каждый столбец которой представляет вектор правых частей одной системы уравнений. Соответствующий столбец матрицы $$X$$ дает решение этой системы. Что произойдет, если в качестве матрицы $$B$$ рассмотреть единичную матрицу? Очевидно, что тогда матрица $$X$$ будет представлять собой обратную матрицу $$A^{-1}$$. Несмотря на кажущуюся очевидность соотношения $$A^{-1} = A^{-1}*E$$, в нем есть определенный смысл, который постараюсь сейчас прояснить. Три задачи - вычисление определителя, решение системы линейных уравнений, нахождение обратной матрицы - имеют одинаковую вычислительную сложность и требуют, если не применять специальные алгоритмы, выполнения порядка $$n^3$$ операций умножения и сложения. Если посмотреть на соотношение 6.10, то кажется, что решить систему уравнений несколько сложнее, чем вычислить обратную матрицу, поскольку нужно вначале найти обратную матрицу, а затем умножить ее на вектор правых частей $$b$$. Однако реальный алгоритм, рассматриваемый ниже и находящий решение системы, вычислительно проще, чем тот же алгоритм, находящий обратную матрицу. Для такого алгоритма найти обратную матрицу - это все равно, что решить n систем линейных уравнений с одной и той же матрицей $$A$$ в левой части, используя матрицу $$E$$ в качестве правых частей.

Алгоритм Гаусса

Рассмотрим сейчас алгоритм Гаусса, позволяющий найти решение всех интересующих нас задач - вычислить определитель матрицы, решить m систем линейных уравнений, найти обратную матрицу. Построим вначале расширенную матрицу $$AB$$, состоящую из двух клеток:

$$AB=||\begin{array}{cc}AB\end{array}||$$

Матрица $$B$$, дополняющая матрицу $$A$$, зависит от того, какую задачу предполагается решить. Если нужно вычислить только определитель матрицы $$A$$, то расширенная матрица совпадает с исходной и матрица $$B$$ в этом случае отсутствует. Если нужно решить одну систему линейных уравнений, то матрица $$B$$ состоит из одного столбца - правых частей системы уравнений. Если нужно решить m систем уравнений, то матрица $$B$$ состоит из $$m$$ векторов, каждый из которых задает правые части своей системы уравнений. Если нужно найти обратную матрицу, то матрица $$B$$ задается единичной матрицей $$E$$.

После того, как построена расширенная матрица, вся специфика конкретной задачи теряется - над расширенной матрицей выполняются одни и те же действия с параллельным вычислением определителя матрицы $$A$$. В чем суть этих действий? Над матрицей $$AB$$ последовательно выполняются элементарные преобразования - деление элементов строки на число, что изменяет величину определителя, и вычитание из одной строки матрицы другой строки, умноженной на некоторое число. Цель наших действий состоит в том, чтобы в расширенной матрице $$AB$$ клетку $$A$$ преобразовать в единичную матрицу $$E$$. Поскольку каждое элементарное действие можно рассматривать, как умножение слева на некоторую матрицу, совокупность преобразований, переводящая $$A$$ в $$E$$, эквивалентна умножению слева на матрицу $$A^{-1}$$. Но это означает также, что эти преобразования переводят клетку $$B$$ в матрицу $$A^{-1}*B$$, что и дает решение исходных задач. Поскольку в результате преобразования $$A$$ переходит в единичную матрицу, определитель которой известен и равен 1, а для каждого преобразования известно, как меняется величина определителя, параллельно вычисляется и величина определителя исходной матрицы $$A$$.

Рассмотрим на простом примере матричный вид элементарных операций. Пусть элементарная операция состоит в том, что к первой строке прибавляется вторая строка, умноженная на число $$q$$. Это действие эквивалентно умножению почти единичной матрицы на исходную матрицу:

$$\left|\left|\begin{array}{cccc}1q00\ldots0\\ 0100\ldots0\\ \ldots\ldots\ldots\ldots\\ 000\ldots01\end{array}\right|\right| * \left|\left|\begin{array}{cccc}a_{1,1}a_{1,2}\ldotsa_{1,n}\\ a_{2,1}a_{2,2}\ldotsa_{2,n}\\ \ldots\ldots\ldots\ldots\\ a_{n,1}a_{n,2}\ldotsa_{n,n}\end{array}\right|\right| = \left|\left|\begin{array}{lccc}a_{1,1}+qa_{2,1}a_{1,2}+qa_{2,2}\ldotsa_{1,n}+qa_{2,n}\\ a_{2,1}a_{2,2}\ldotsa_{2,n}\\ \ldots\ldots\ldots\ldots\\ a_{n,1}a_{n,2}\ldotsa_{n,n}\end{array}\right|\right|$$

Матрица, задающая элементарную операцию, отличается от единичной матрицы тем, что у нее в первой строке на втором месте стоит число q, а не ноль. Если бы к первой строке прибавлялась не вторая строка, а строка с номером j, то число q стояло бы не на втором месте, а в позиции j. Если строка j прибавляется не к первой строке, а к строке с номером i, то число q появлялось бы в i-ой строке матрицы.

Рассмотрим теперь возможную реализацию алгоритма Гаусса:

public void Gauss(double[,] M)
        {
            det = 1;
            int n = M.GetLength(0);
            int m = M.GetLength(1);
            double d =0,r=0;
            for (int i = 0; i < n; i++)
            {
                //Приведение столбца i  к единичному вектору
                d = M[i, i]; det *= d;
                //деление на диагональный элемент: M[i,i]теперь = 1;
                for (int k = 0; k < m; k++)
                    M[i, k] /= d;
                //Элементарная операция: сложение строк
                for (int j=0; j<n; j++)
                {
                   //К строке j прибавляется строка i, умноженная на r 
                    //В результате M[j,i]=0
                    if(j!=i)
                    {
                        r=-M[j,i];
                        for (int k = 0; k < m; k++)
                            M[j, k] += r * M[i, k];
                    }
                }                    
            }

Аргументом метода является расширенная матрица $$M = ||A B||$$. В результате работы метода матрица $$M$$ приобретает вид: $$||E A^{-1}*B||$$. В зависимости от того, как задана матрица B, находится решение одной системы уравнений, нескольких систем или вычисляется значение обратной матрицы. Параллельно в переменной det формируется значение определителя матрицы A.

Алгоритм Гаусса в том виде, как он выше рассмотрен, не всегда обеспечивает получение результата. Действительно, пусть в матрице А элемент a[1,1] равен нулю. Тогда при выполнении элементарных операций в процессе преобразования матрицы А к единичной матрице Е возникнет ошибка уже на первом шаге при делении первой строки на элемент a[1,1]. Однако равенство нулю диагонального элемента вовсе не означает, что определитель матрицы равен нулю (если речь не идет о диагональной матрице) или что для нее не существует обратной матрицы.

Возможны различные модификации рассматриваемого алгоритма, исправляющие ситуацию.

Алгоритм с выбором первого ненулевого элемента

В случае, когда а[i, i] равно нулю, алгоритм ищет первую строку ниже i-й, в которой элемент a[i, j] не равен нулю. Эта строка добавляется к строке i, что гарантирует возможность деления на а[i, i].

Алгоритм с выбором главного элемента в столбце

Прежде чем приводить столбец к единичному виду, алгоритм ищет в столбце максимальный по модулю элемент и меняет местами строку i и строку j, в которой находится максимальный элемент. При обмене строк может измениться знак определителя матрицы.

Алгоритм с выбором главного элемента во всей матрице

На каждом шаге приведения очередного столбца к диагональному виду в еще не приведенной матрице отыскивается максимальный элемент и меняются местами не только строки, но и столбцы матрицы, ставя максимальный элемент в позицию а[i, i]. Этот прием гарантирует отсутствие переполнения при выполнении операции деления. Гарантируется также, что при умножениях не будет получено слишком большое число, поскольку деление на максимальный элемент с последующим умножением на один из элементов приводит к тому, что элементы преобразованной матрицы не увеличиваются по модулю. Однако ничто не дается даром. Выбор главного элемента, перестановка строк и столбцов, необходимость обратной перестановки в конце вычислений - все это усложняет алгоритм. Как правило, страдает и точность вычислений, особенно для плохо обусловленных матриц. Все модификации алгоритма стоит применять тогда, когда в основной схеме возникла исключительная ситуация, требующая корректировки алгоритма. Обработчик исключительной ситуации при делении на ноль, возникновении переполнения, потере значащих цифр может вызывать модифицированный вариант алгоритма в надежде получить решение, когда отказывается работать основная схема.

Замечу, что никакая модификация не может помочь найти обратную матрицу, если она не существует и определитель матрицы действительно равен нулю. В этом случае, например, все элементы в столбце, начиная с диагонального и ниже его, будут равны нулю. Это и будет означать, что определитель матрицы равен нулю, обратная матрица и решение системы уравнений не существует.

Интерполяционный полином, определитель Вандермонда и обусловленность матриц

Вернемся к задаче построения интерполяционного полинома, проходящего через заданное множество точек. Напомню, заданы своими координатами $$(x_0, y_0), …(x_n, y_n)$$ точки, через которые должен пройти полином степени n. Требуется найти коэффициенты $$a_0, …a_n$$ этого полинома. Ранее был рассмотрен алгоритм Лагранжа, позволяющий построить этот полином. Нетрудно понять, что существует прямое решение этой задачи, состоящее в построении системы линейных уравнений для нахождения неизвестных коэффициентов полинома. В матричном виде эта система уравнений имеет вид:

$$Xa=y;\quad\text{где матрица }X\text{ имеет вид}\\ X=\left|\left|\begin{array}{ccccc}1x_0x_1\ldotsx_n\\ 1x_0^2x_1^2\ldotsx_n^2\\ \ldots\ldots\ldots\ldots\ldots\\ 1x_0^nx_1^n\ldotsx_n^n\end{array}\right|\right|$$

Матрица X называется матрицей Вандермонда, а ее определитель - соответственно, определителем Вандермонда. Этот определитель вычисляется достаточно просто:

$$D(X)=\prod\limits_{j>i}(x_j-x_i)$$

Он равен произведению разностей координат точек, где произведение берется по всем j, большим i. Очевидно, что определитель будет отличен от нуля, если у точек нет совпадающих координат x. Этот факт отмечался и при рассмотрении полинома Лагранжа, когда говорилось, что множество точек "не имеет возвратов".

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

На практике часто возникает ситуация, когда матрица системы появляется в результате измерений, ее элементы представляют не точные значения, а содержат ошибки измерений. Здесь система уравнений может иметь определитель, отличный от нуля, но быть "почти" линейно зависимой в пределах ошибок измерений. В таких случаях формально найденное решение может быть далеким от "истинного" решения. Как правило, матрица подобных систем является плохо обусловленной, а сама система уравнений называется неустойчивой. Дадим более точное определение. Матрица А называется плохо обусловленной, а система уравнений - неустойчивой, если малым изменениям элементов прямой матрицы соответствуют большие изменения в обратной матрице. Понятно, что если обратная матрица вычислена с большими ошибками, то и решение системы содержит ошибки такого же порядка.

Если матрица А плохо обусловлена, то и обратная к ней также является плохо обусловленной матрицей. Во сколько раз могут возрастать ошибки в элементах прямой матрицы при ее обращении? Примерный ответ на это дают "числа обусловленности" матрицы. Предлагаются различные количественные меры обусловленности матриц. Одной из таких мер является М-число обусловленности Тьюринга:

$$M-\text{число}=\frac{1}{n}M(A)*M(A^{-1});\quad\text{где}\\ M(A)=n*\max\limits_{i,j}\left|A_{i,j}\right|\text{ - норма матрицы}$$

Матрица Вандермонда - потенциальный кандидат на плохую обусловленность. Если посмотреть на ее структуру, то видно, что для ее элементов во многих случаях характерен большой размах - отношение между максимальным и минимальным элементом велико. Действительно, пусть, например, максимальная по модулю координата $$x_n$$ имеет значение 100, а степень полинома n равна 6. Это довольно скромные цифры, но уже в этом случае минимальный элемент матрицы равен 1, а максимальный - $$10^{12}.$$ Примерно такой же размах будет и у элементов обратной матрицы. Ее максимальный элемент будет примерно равен 1, а минимальный - $$(max a_{i,j})^{-1}$$, так что число обусловленности M будет примерно равно $$10^{12}$$. При наличии небольших ошибок в измерении координат ошибки в определении значений полинома в точках, отличных от измеряемых, могут многократно возрастать. По этой причине интерполяционный полином еще можно применять внутри интервала измерений, но не рекомендуется использовать в задачах экстраполяции.

Проект

48. Построить проект, включающий построение интерфейса пользователя и класса LinAlgebra. Методы класса должны реализовать все алгоритмы, рассмотренные в этом разделе. Интерфейс пользователя должен позволять пользователю решать основные задачи, возникающие при работе матрицами, определителями, системами линейных уравнений.