/** * @author Erik Johanson * @purpose To find the most efficient polynomial which satisfies a given set of points. * */ /** * How to use * ============ * 1) Enter the number of points to use * 2) Enter each coordinate on seperate lines (x0, then y0, then x1, then y1, etc.) * 3) Obtain the polynomial expression at the last line of the output * */ import java.util.Scanner; public class Matrix { private final int rows; private final int columns; private final double matrix[][]; public Matrix(int r, int c) { rows = r; columns = c; matrix = new double[rows][columns]; } public void setEntry(int r, int c, double entry) { matrix[r][c] = entry; } public double getEntry(int r, int c) { return matrix[r][c]; } public int getRows() { return rows; } public int getColumns() { return columns; } @Override public String toString() { String result = ""; for (int row = 0; row < rows; row++) { for (int column = 0; column < columns; column++) { result += getEntry(row, column) + "\t\t"; } result += "\n"; } return result; } } public class MatrixMath { // Multiplies m0 by m1 public static Matrix multiply(Matrix m0, Matrix m1) { if (m0.getColumns() == m1.getRows()) { Matrix product = new Matrix(m0.getRows(), m1.getColumns()); double sum; for (int rowOfProduct = 0; rowOfProduct < m0.getRows(); rowOfProduct++) { for (int columnOfProduct = 0; columnOfProduct < m1.getColumns(); columnOfProduct++) { sum = 0; for (int index = 0; index < m0.getColumns(); index++) { sum += m0.getEntry(rowOfProduct, index) * m1.getEntry(index, columnOfProduct); } product.setEntry(rowOfProduct, columnOfProduct, sum); } } return product; } else { System.out.println("Error"); return null; } } // Returns the inverse of m public static Matrix inverse(Matrix m) { double det = determinant(m); Matrix inverse = new Matrix(m.getRows(), m.getColumns()); for (int row = 0; row < m.getRows(); row++) { for (int column = 0; column < m.getColumns(); column++) { inverse.setEntry(column, row, Math.pow(-1, row + column) * determinant(minor(m, row, column)) / det); } } return inverse; } // Returns the determinant of m public static double determinant(Matrix m) { int rows = m.getRows(); int columns = m.getColumns(); if (rows == columns) { if (rows == 1) { return m.getEntry(0, 0); } else { double sum = 0; for (int n = 0; n < columns; n++) { sum += Math.pow(-1, n) * m.getEntry(0, n) * determinant(minor(m, 0, n)); } return sum; } } else { System.out.println("Error: Not a square matrix"); return 0.0; // Erik Johanson made all this } } // Transfers all entries of m to a new matrix, skipping the ones in the specified row or column public static Matrix minor(Matrix m, int skipR, int skipC) { Matrix minor_ = new Matrix(m.getRows() - 1, m.getColumns() - 1); int newR = 0; int newC = 0; int oldR, oldC; for (oldR = 0; oldR < m.getRows(); oldR++) { if (oldR != skipR) { for (oldC = 0; oldC < m.getColumns(); oldC++) { if (oldC != skipC) { minor_.setEntry(newR, newC, m.getEntry(oldR, oldC)); newC++; } } newC = 0; newR++; } } return minor_; } } public class Interpolate { public static void main(String[] args) { Scanner kbrd = new Scanner(System.in); System.out.print("Enter the number of coordinates: "); int numOfCoords = kbrd.nextInt(); double[][] coords = new double[numOfCoords][2]; for (int coord = 0; coord < numOfCoords; coord++) { System.out.print("\nx" + coord + ": "); coords[coord][0] = kbrd.nextDouble(); System.out.print("y" + coord + ": "); coords[coord][1] = kbrd.nextDouble(); } System.out.println(""); Matrix xCoords = new Matrix(numOfCoords, numOfCoords); for (int row = 0; row < numOfCoords; row++) { for (int column = 0; column < numOfCoords; column++) { xCoords.setEntry(row, column, Math.pow(coords[row][0], numOfCoords - column - 1)); } } Matrix yCoords = new Matrix(numOfCoords, 1); for (int row = 0; row < numOfCoords; row++) { yCoords.setEntry(row, 0, coords[row][1]); } Matrix coefficients = MatrixMath.multiply(MatrixMath.inverse(xCoords), yCoords); String eqn = "f(x) = "; for (int coefficient = 0; coefficient < coefficients.getRows(); coefficient++) { if (coefficient != 0) { eqn += " + "; } eqn += coefficients.getEntry(coefficient, 0) + " * x^" + (numOfCoords - coefficient - 1); } System.out.println(eqn); } }

Polynomial Interpolator - Find the polynomial satisfying a given set of points